[BZOJ3028]食物

题目链接：

BZOJ3028.

生成函数模板题（Luogu2000也差不多，可以一做，稍难）

对每种食物求生成函数乘起来：

• 承德汉堡：偶数个

(sum_{i=2j,jin mathbb{N}}^inftylimits x^i=frac{1}{1-x^2})

• 可乐：0个或1个

(sum_{i=0}^1 x^i=1+x=frac{1-x^2}{1-x})

• 鸡腿：0个，1个或2个

(sum_{i=0}^2 x^i=frac{1-x^3}{1-x})

• 蜜桃多：奇数个

(sum_{i=2*j+1,jinmathbb{N}}^inftylimits x^i=xsum_{i=2j,jin mathbb{N}}^inftylimits x^i=frac{x}{1-x^2})

• 鸡块：4的倍数个

(sum_{i=4j,jin mathbb{N}}^inftylimits x^i=frac{1}{1-x^4})

• 包子：0个，1个，2个或3个

(sum_{i=0}^3 x^i=frac{1-x^4}{1-x})

• 土豆片炒肉：不超过一个

(sum_{i=0}^1 x^i=1+x=frac{1-x^2}{1-x})

• 面包：3的倍数个

(sum_{i=3j,jin mathbb{N}}^inftylimits x^i=frac{1}{1-x^3})

全部乘起来，化简得：(frac{x}{(1-x)^4})

(ecause frac{1}{(1-x)^4}=sum_{i=0}^inftylimits C_{3}^{i+3}x^i)

( herefore frac{x}{(1-x)^4}=sum_{i=0}^inftylimits C_{3}^{i+3}x^{(i+1)})

求第(n)项，则(n=i+1,i=n-1)，系数即答案为(C_3^{n+2})

代码：

#include <cstdio>
#include <cctype>

int n;
const int Mod=10007;

int Pow(int a,int b)
{
	int Res=1;
	for(;b;b>>=1,a=a*a%Mod)
		if(b&1)Res=Res*a%Mod;
	return Res%Mod;
}

int main()
{
	for(int c;isdigit(c=getchar());n=(n*10+(c^48))%Mod);
	printf("%d
",int((long long)n*(n+1)*(n+2)*Pow(6,Mod-2)%Mod));
	return 0;
}