题解：P10780 BZOJ3028 食物

胡金梁 · 2024-11-19 09:52:49 · 题解

组合题、个数、累和……能想到生成函数。

仔细看一下，发现这题的生成函数很模版，可以依次求生成函数，再累乘。

承德汉堡：f_1(x)=x^0+x^2+…+x^{2k}+…=\frac{1}{1-x^2}在无穷累和且0<x<1的情况下这个等式是恒成立的，移项即可证明。

同理，鸡腿：f_2(x)=x^0+x^1+x^2，可乐：f_3(x)=x^0+x^1，包子：f_4(x)=x^0+x^1+x^2+x^3，土豆片炒肉:f_5(x)=x^0+x^1。

鸡块：f_6(x)=x^0+x^4+…+x^{4k}+…=\frac{1}{1-x^4}

蜜桃多：f_7(x)=x^1+x^3+…+x^{2k+1}+…=\frac{x}{1-x^2}

面包：f_8(x)=x^0+x^3+…+x^{3k}+…=\frac{1}{1-x^3}

所以总的也就是：f(x)=\sum_{i=1}^{8}f_i(x)=\frac{x(x^0+x^1)^2(x^0+x^1+x^2)(x^0+x^1+x^2+x^3)}{(1-x^2)^2(1-x^3)(1-x^4)}=\frac{x(1-x^2)^2(1-x^3)(1-x^4)}{(1-x)^4}\times\frac{1}{(1-x^2)^2(1-x^3)(1-x^4)}=\frac{x}{(1-x)^4}=x(1+x+x^2+x^3+…+x^k+…)^4

现在要取n次项的系数，可以将问题转化为：把n-1个小球放入4个格子中，格子允许为空，求方案数。

由插板法，可以得知答案为C^{4-1}_{n-1+4-1}=\frac{n(n+1)(n+2)}{3!}

代码如下：

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
const int mod=1e4+7;
int ksm(int a,int b)
{
    int re=1;
    while(b)
    {
        if(b&1)
        {
            re*=a;
            re%=mod;
        }
        a*=a;
        a%=mod;
        b/=2;
    }
    return re;
}
signed main(){
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=0;
    char ch;
    while(cin>>ch)
    {
        n=(n*10+ch-'0')%mod;
    }
    cout<<n*(n+1)%mod*(n+2)%mod*ksm(6,mod-2)%mod;
#if __MY_TEST__
    fclose(stdin);
    fclose(stdout);
#endif
}