BZOJ3028 食物（生成函数）

时间：2023-03-09 03:06:16
BZOJ3028 食物（生成函数）

　　显然构造出生成函数：则有f(x)=(1+x2+x4+……)·(1+x)·(1+x+x2)·(x+x3+x5+……)·(1+x4+x8+……)·(1+x+x2+x3)·(1+x)·(1+x3+x6+……)。

　　化为有限，则有f(x)=x(1+x)2·(1+x+x2)·(1+x+x2+x3)/(1-x2)2·(1-x3)·(1-x4)=x·(1+x+x2)·(1+x)/(1-x)2·(1-x3)·(1-x2)=x·(1+x)/(1-x)3·(1-x2)=x/(1-x)4。

　　广义二项式定理暴算。则有f(x)=x·(C(-4,0)·(-x)0+C(-4,1)·(-x)1+……)。考虑C(-4,n)=(-4)·(-5)·……·(-4-n+1)/n!=(-1)n·(n+3)!/3!/n!=(-1)n·C(n+3,3)。则f(x)=C(3,3)·x+C(4,3)·x2+……。

　　即答案为C(n+2,3)=n(n-1)(n-2)/6。求一下6在模10007下的逆元就好。观察到6整除10008甚至可以直接算逆元。

　　（怎么我一交darkbzoj就上不去了

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define p 10007

int read()

{

    int x=;char c=getchar();

    while (c>=''&&c<='') x=((x<<)+(x<<)+(c^))%p,c=getchar();

    return x;

}

int n;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3028.in","r",stdin);

    freopen("bzoj3028.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read()+;

    cout<<n*(n+p-)%p*(n+p-)%p*%p;

    return ;

}

相关文章