1290.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1290 on 2006-06-24 at 16:53:12 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 51;
const int L = 128;

class BigInt {
private:
	void update();
public:
	int v[L], len;
	BigInt() : len(0) { memset(v, 0, sizeof(v)); }
	void set(int n) { v[0] = n; len = 1; }
	BigInt operator *(const int) const;
	BigInt operator +(const BigInt&) const;
	void print() const;
};
void BigInt::update() {
	int i;
	for(i = 0; i < len; i++) {
		int rv = v[i] / 10; v[i] %= 10;
		if(rv != 0) len = max(len, i+2);
		v[i+1] += rv;
	}
}
BigInt BigInt::operator *(const int d) const {
	int i; BigInt r = *this;
	for(i = 0; i < r.len; i++) r.v[i] *= d;
	r.update();
	return r;
}
BigInt BigInt::operator +(const BigInt& bi) const {
	int i; BigInt r = *this;
	for(i = 0; i < bi.len; i++) r.v[i] += bi.v[i];
	r.len = max(r.len, bi.len); r.update();
	return r;
}
void BigInt::print() const {
	if(len == 0) putchar('0');
	int i;
	for(i = len-1; i >= 0; i--) printf("%d", v[i]);
	putchar('\n');
}

int main()
{
	int n, m, i, j, t, T;
	BigInt c[N][N];

	c[0][0].set(1);
	for(i = 1; i < N; i++)
		for(j = 1; j <= i; j++)
			c[i][j] = c[i-1][j-1]*(2*i-j)+c[i-1][j]*j;
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		if(m > n) printf("0\n");
		else c[n][m].print();
	}
	
	return 0;
}