bzoj 3208 食物(生成函数)

先推一下生成函数
承德汉堡：偶数个
1+x2+x4+x6+......=11−x2$1+x^2+x^4+x^6+......=\frac{1}{1-x^2}$
可乐：0个或1个
1+x=1−x21−x$1+x=\frac{1-x^2}{1-x}$
鸡腿：0个或1个或2个
1+x+x2=1−x31−x$1+x+x^2=\frac{1-x^3}{1-x}$
蜜桃多：奇数个
x+x3+x5+......=x1−x2$x+x^3+x^5+......=\frac{x}{1-x^2}$
鸡块：四的倍数个
1+x4+x8+x12+......=11−x4$1+x^4+x^8+x^{12}+......=\frac{1}{1-x^4}$
包子：0个或1个或2个或3个
1+x+x2+x3=1−x41−x$1+x+x^2+x^3=\frac{1-x^4}{1-x}$
土豆片炒肉：不超过一个
1+x=1−x21−x$1+x=\frac{1-x^2}{1-x}$
面包：三的倍数个
1+x3+x6+x9+......=11−x3$1+x^3+x^6+x^9+......=\frac{1}{1-x^3}$
总生成函数：
11−x2×1−x21−x×1−x31−x×x1−x2×11−x4×1−x41−x×1−x21−x×11−x3=x(1−x)4$\frac{1}{1-x^2}\times \frac{1-x^2}{1-x}\times \frac{1-x^3}{1-x}\times \frac{x}{1-x^2}\times \frac{1}{1-x^4}\times \frac{1-x^4}{1-x}\times \frac{1-x^2}{1-x}\times \frac{1}{1-x^3}=\frac{x}{{(1-x)}^4}$
跟据广义二项式定理答案即为xn−1$x^{n-1}$的系数
ans=Cn−1n−1+3=n∗(n+1)∗(n+2)6$ans=C_{n-1+3}^{n-1}=\frac{n\ast (n+1)\ast (n+2)}{6}$

所以可以边读边膜，代码如下：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 10007
using namespace std;

string tmp;
long long n;

long long inv(long long a)
{
    int b=mod-2,ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main()
{
    cin>>tmp;
    for(int i=0;i<tmp.length();i++)
    {
        n=(n*10+tmp[i]-'0')%mod;
    }
    printf("%lld\n",((n*(n+1)%mod)*(n+2)%mod)*inv(6)%mod);
}