bzoj3028:食物（生成函数）

传送门
生成函数模板题。

我们直接把每种食物的生成函数列出来&＃xff1a;
承德汉堡&＃xff1a;1&＃43;x2&＃43;x4&＃43;...&＃61;11−x21&＃43;x^2&＃43;x^4&＃43;...&＃61;\frac 1{1-x^2}1&＃43;x2&＃43;x4&＃43;...&＃61;1−x21​
可乐&＃xff1a;1&＃43;x&＃61;1−x21−x1&＃43;x&＃61;\frac{1-x^2}{1-x}1&＃43;x&＃61;1−x1−x2​
鸡腿&＃xff1a;1&＃43;x&＃43;x2&＃61;1−x31−x1&＃43;x&＃43;x^2&＃61;\frac{1-x^3}{1-x}1&＃43;x&＃43;x2&＃61;1−x1−x3​
蜜桃多&＃xff1a;x&＃43;x3&＃43;x5&＃43;...&＃61;x(1&＃43;x2&＃43;x4&＃43;...)&＃61;x1−x2x&＃43;x^3&＃43;x^5&＃43;...&＃61;x(1&＃43;x^2&＃43;x^4&＃43;...)&＃61;\frac x{1-x^2}x&＃43;x3&＃43;x5&＃43;...&＃61;x(1&＃43;x2&＃43;x4&＃43;...)&＃61;1−x2x​
鸡块&＃xff1a;1&＃43;x4&＃43;x8&＃43;x12&＃43;...&＃61;11−x41&＃43;x^4&＃43;x^8&＃43;x^{12}&＃43;...&＃61;\frac 1{1-x^4}1&＃43;x4&＃43;x8&＃43;x12&＃43;...&＃61;1−x41​
包子&＃xff1a;1&＃43;x&＃43;x2&＃43;x3&＃61;1−x41−x1&＃43;x&＃43;x^2&＃43;x^3&＃61;\frac{1-x^4}{1-x}1&＃43;x&＃43;x2&＃43;x3&＃61;1−x1−x4​
土豆片炒肉&＃xff1a;1&＃43;x&＃61;1−x21−x1&＃43;x&＃61;\frac{1-x^2}{1-x}1&＃43;x&＃61;1−x1−x2​
面 包&＃xff1a;1&＃43;x3&＃43;x6&＃43;x9&＃43;...&＃61;11−x31&＃43;x^3&＃43;x^6&＃43;x^9&＃43;...&＃61;\frac 1{1-x^3}1&＃43;x3&＃43;x6&＃43;x9&＃43;...&＃61;1−x31​
把所有的乘起来&＃xff1a;f(x)&＃61;x(1−x)4&＃61;x(1&＃43;x&＃43;x2&＃43;...)4f(x)&＃61;\frac x{(1-x)^4}&＃61;x(1&＃43;x&＃43;x^2&＃43;...)^4f(x)&＃61;(1−x)4x​&＃61;x(1&＃43;x&＃43;x2&＃43;...)4
我们要求xnx^nxn的系数。
也就是求g(x)&＃61;(1&＃43;x&＃43;x2&＃43;...)4g(x)&＃61;(1&＃43;x&＃43;x^2&＃43;...)^4g(x)&＃61;(1&＃43;x&＃43;x2&＃43;...)4的xn−1x^{n-1}xn−1的系数。
相当于求将$n-1$拆成四个自然数的方案数&＃xff0c;这个组合数学搞定Ans&＃61;Cn&＃43;23Ans&＃61;C_{n&＃43;2}^3Ans&＃61;Cn&＃43;23​
代码&＃xff1a;

#include
using namespace std;
const int mod&＃61;10007;
int n&＃61;0;
int main(){char ch&＃61;getchar();while(!isdigit(ch))ch&＃61;getchar();while(isdigit(ch))n&＃61;((n<<3)&＃43;(n<<1)&＃43;(ch^48))%mod,ch&＃61;getchar();cout<<n*(n&＃43;1)%mod*(n&＃43;2)%mod*1668%mod;return 0;
}