传送门
生成函数模板题。
我们直接把每种食物的生成函数列出来:
承德汉堡:1+x2+x4+...=11−x21+x^2+x^4+...=\frac 1{1-x^2}1+x2+x4+...=1−x21
可乐:1+x=1−x21−x1+x=\frac{1-x^2}{1-x}1+x=1−x1−x2
鸡腿:1+x+x2=1−x31−x1+x+x^2=\frac{1-x^3}{1-x}1+x+x2=1−x1−x3
蜜桃多:x+x3+x5+...=x(1+x2+x4+...)=x1−x2x+x^3+x^5+...=x(1+x^2+x^4+...)=\frac x{1-x^2}x+x3+x5+...=x(1+x2+x4+...)=1−x2x
鸡块:1+x4+x8+x12+...=11−x41+x^4+x^8+x^{12}+...=\frac 1{1-x^4}1+x4+x8+x12+...=1−x41
包子:1+x+x2+x3=1−x41−x1+x+x^2+x^3=\frac{1-x^4}{1-x}1+x+x2+x3=1−x1−x4
土豆片炒肉:1+x=1−x21−x1+x=\frac{1-x^2}{1-x}1+x=1−x1−x2
面 包:1+x3+x6+x9+...=11−x31+x^3+x^6+x^9+...=\frac 1{1-x^3}1+x3+x6+x9+...=1−x31
把所有的乘起来:f(x)=x(1−x)4=x(1+x+x2+...)4f(x)=\frac x{(1-x)^4}=x(1+x+x^2+...)^4f(x)=(1−x)4x=x(1+x+x2+...)4
我们要求xnx^nxn的系数。
也就是求g(x)=(1+x+x2+...)4g(x)=(1+x+x^2+...)^4g(x)=(1+x+x2+...)4的xn−1x^{n-1}xn−1的系数。
相当于求将n−1n-1n−1拆成四个自然数的方案数,这个组合数学搞定Ans=Cn+23Ans=C_{n+2}^3Ans=Cn+23
代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int n=0;
int main(){
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))n=((n<<3)+(n<<1)+(ch^48))%mod,ch=getchar();
cout<<n*(n+1)%mod*(n+2)%mod*1668%mod;
return 0;
}