[bzoj 3028] 食物

8种物品, 同一种物品之间不可区分, 求总共n件物品, 每种物品分别满足以下数量限制的方案数模10007: - 偶数 - 0或1 - 0,1,或2 - 奇数 - 4的倍数 - 0,1,2,或3 - 不超过1 - 3的倍数

(1≤n≤10^500) 看到代码非常短 为了练习一下生成函数, 来水一发......

方案数的生成函数是

而

所以 前的系数为

逐个字符读入, 边读入边取模即可. 10^5+7 是质数, 6存在逆元.

const int MOD = 10007;
int main()
{
	char c;
	int n = 0;
	while (c = getchar(), !isdigit(c)) ;
	n = c - '0';
	while (c = getchar(), isdigit(c)) n = (n*10 + c - '0') % MOD;
	printf("%lld\n", 1LL * n * (n+1) * (n+2) * 1668 % MOD);
	return 0;
}