排列组合（二）(指数型母函数).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 62 行

#include<iostream>
using namespace std;
int mm[1000][100];
__int64 a[1000], b[1000];

inline __int64 gcd(__int64 x, __int64 y) //求公约数
{
	__int64 temp;
	while (x % y) {
		temp = x % y;
		x = y;
		y = temp;
	}
	return y;
}

int main() {
	int n, m, i, j, k;
	__int64 tmp, tmp1;
	while (scanf("%d %d", &n, &m) != EOF) {
		for (i = 0; i < n; i ++) {
			scanf("%d", &mm[i][0]);
			for (j = 1; j <= mm[i][0]; j ++)
				scanf("%d", &mm[i][j]);
		}
		memset(a, 0, sizeof(__int64)*(m + 1));
		for (i = 1; i <= mm[0][0]; i ++)
			a[mm[0][i]] = 1;
		for (i = 1; i < n; i ++) {
			memset(b, 0, sizeof(__int64)*(m + 1));
			for (j = 0; j <= m; j ++)
				for (k = 1;j + mm[i][k] <= m && k <= mm[i][0]; k ++) {
					if (mm[i][k] != 0) {
						tmp = 1; tmp1 = 1;
						int w = j + mm[i][k];
						int x = mm[i][k] < j ? mm[i][k] : j; // x 是较小的数
						int y = w - x;

						__int64 z;
						while (w > y) {
							tmp *= w;
							tmp1 *= x;
							z = gcd(tmp, tmp1);
							if (z > 1) {
								tmp /= z;
								tmp1 /= z;
							}
							w--;
							x--;
						}

						b[j + mm[i][k]] += tmp * a[j];
					}
				}
			for (j = 0; j <= m; j ++)
				a[j] += b[j];
		}
		printf("%I64d\n", a[m]);
	}
	return 0;
}