bzoj 3028: 食物【生成函数】

承德汉堡：( 1+x^2+x4+...=frac{1}{1-x^2} )
可乐：(1+x )
鸡腿：( 1+x+x^2=frac{x3-1}{x-1} )
蜜桃多：( x+x^3+x5+...=frac{x}{1-x^2} )
鸡块：( 1+x^4+x8+...=frac{1}{1-x^4} )
包子：( 1+x+x^2+x3=frac{x^4-1}{x-1} )
土豆片炒肉：( 1+x )
面包：( 1+x^3+x6+x^{9+...=frac{1}{1-x}3} )
乘起来是( frac{x}{(1-x)^4} )
然后根据某公式，生成函数( frac{1}{(1-x)^n}=(1+x+x2+x^3+...)n )，求m项系数就相当于组合数( C_{n+m-1}^{n-1} )
然后乘上x就相当于右移一位，就变成了( C_{n+m-2}^{n-1} )，要求第n位，答案就是( C_{n+2}^{3} )

#include<iostream>
#include<cstdio>
#define mod 10007
using namespace std;
const int N=505;
int n;
char s[N];
int main()
{
	scanf("%s",s+1);
	for(int i=1;s[i];i++)
		n=(n+(n<<1)+(n<<3)+(s[i]-'0'))%mod;
	printf("%d
",(n*(n+1)%mod*(n+2)%mod*1668%mod));
	return 0;
}