题面：BZOJ传送门
题目让我们求这些物品在合法范围内任意组合，一共组合出$n$个物品的方案数
考虑把每种食物都用生成函数表示出来，然后用多项式乘法把它们乘起来，第$n$项的系数就是方案数
汉堡：$1+x^{2}+x^{4}+x^{4}...=\frac{1}{1-x^{2}}$
可乐：$1+x$
鸡腿：$1+x+x^{2}$
蜜桃：$x+x^{3}+x^{5}+x^{7}...=\frac{x}{1-x^{2}}$
鸡块：$1+x^{4}+x^{8}+x^{12}..=\frac{1}{1-x^{3}}$
包子：$1+x+x^{2}+x^{3}=(1+x)(1+x^{2})$
土豆：$1+x$
面包：$1+x^{3}+x^{6}+x^{9}...=\frac{1}{1-x^{3}}$
数据范围非常大，直接上生成函数会炸，而且模数也不支持$NTT$
把这些多项式乘起来，化简可得$f(x)=\frac{x}{(1-x)^{4}}$
一种做法是求导，再代入泰勒展开，然而我太弱了并没有推明白式子
$f(x)=\frac{x}{(1-x)^{4}}=x(\frac{1}{(1-x)})^{4}$
考虑$\frac{1}{1-x}$的本质，就是$1+x+x^{2}+x^{3}...$
而它的四次方就是$1+4x+10x^{2}+20x^{3}..$
即$C_{3}^{0}+C_{4}^{1}x+C_{5}^{2}x^{2}+C_{6}^{3}x^{3}...$
这不就是个躺着的杨辉三角么，那么第$n$项的结果就是$C_{n+3}^{n}$
然而还有一项$x$没算进去，相当于把整个多项式右移一位，即答案左移一位
最终答案变成了$C_{n+2}^{n-1}$
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define ll long long 6 #define dd double 7 #define N1 1010 8 using namespace std; 9 10 const int mod=10007; 11 12 int gint() 13 { 14 int ret=0,fh=1; char c=getchar(); 15 while(c<‘0‘||c>‘9‘){if(c==‘-‘)fh=-1;c=getchar();} 16 while(c>=‘0‘&&c<=‘9‘){ret=ret*10+c-‘0‘;c=getchar();} 17 return ret*fh; 18 } 19 20 void exgcd(ll a,ll b,ll &x,ll &y) 21 { 22 if(!b){ x=1; y=0; return; } 23 exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; 24 } 25 char str[N1]; 26 int a[N1],n; 27 28 int main() 29 { 30 scanf("%s",str+1); 31 int ret=0,i; n=strlen(str+1); 32 for(i=1;i<=n;i++) ret=(ret*10+str[i]-‘0‘)%mod; 33 ll inv,invy; ret=1ll*(ret+2)*(ret+1)%mod*(ret)%mod; 34 exgcd(2,mod,inv,invy); inv=(inv%mod+mod)%mod; ret=1ll*ret*inv%mod; 35 exgcd(3,mod,inv,invy); inv=(inv%mod+mod)%mod; ret=1ll*ret*inv%mod; 36 printf("%d\n",ret); 37 return 0; 38 }
原文：https://www.cnblogs.com/guapisolo/p/10326125.html