POJ3734 Blocks

传送门


最近开始加强生成函数。

学完级数后，感觉生成函数就是将几个级数相乘，然后收敛成某个函数后进行化简，最后再用常用级数展开式或者广义二项式定理展开，得到新的级数，那么(m)次项的系数就是和为(m)的方案数。


对于这道题，因为有选择顺序的不同，所以要用指数型生成函数。蓝，黄色的生成函数都是(e^x)，红，绿色只能是偶数，那就是(f(x)=sumlimits_{n=0}^{infty} frac{(2n)!}{x^{2n}}=frac{e^x+e^{-x}}{2}).

将上述四个生成函数相乘，就是总方案数的生成函数(F(x))，

[egin{align*} F(x) &= e^{2x} * (frac{e^x+e^{-x}}{2})^2\ &= frac1{4}(e^{4x}+2e^{2x}+1)\ &= frac1{4}[sum_{n=0}^{infty} frac1{n!}(4x)^n+2sum_{n=0}^{infty}frac1{n!}(2x)^n+1]\ end{align*}]

那么(n)次方项的系数就是(frac{4^n+2^{n+1}}{4n!})，再乘以(n!)即答案。

#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod = 10007;

ll quickpow(ll a, ll b)
{
	ll ret = 1;
	for(; b; b >>= 1, a = a * a % mod)
		if(b & 1) ret = ret * a % mod;
	return ret;
}

int main()
{
	int T; scanf("%d", &T); 
	ll inv4 = quickpow(4, mod - 2);
	while(T--)
	{
		int n; scanf("%d", &n);
		printf("%lld
", (quickpow(4, n) + quickpow(2, n + 1)) % mod * inv4 % mod);
	}
	return 0;
}