题意

把正整数M分解成至多N份且每份不为0（注意1+2+3与2+3+1是不一样的即存在顺序性），一份x的价值是f(x)=a2∗x∗x+a1∗x+a0，总价值为每一份价值的乘积。求所有情况下总价值的和，答案模mo。 M<=10000，mo<=255，N<=108，a2<=4，a1<=300，a0<=100

分析

设g[i,j]表示j个糖果分成了i份的总价值和,f[i]表示一个小朋友分i个糖果的价值

显然有g[i,j]=∑j−1k=1g[i−1,j−k]∗f[k]

明显这是一个卷积的形式

但我们要求的是∑mi=1g[i,m]

那么我们就设一个p[i,j]=∑ik=1g[k,j]

p[i,j]=p[i2,j]+∑i2k=1g[i2+k,j]

p[i,j]=p[i2,j]+∑i2k=1∑j−1l=1g[k,l]∗g[i2,j−l]

p[i,j]=p[i2,j]+∑j−1l=1∑i2k=1g[k,l]∗g[i2,j−l]

p[i,j]=p[i2,j]+∑j−1l=1p[i2,l]∗g[i2,j−l]

显然右边也是一个卷积的形式，递归求出即可。

时间复杂度O(mlogmlogn)

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<complex> #include<cmath> #define pi acos(-1) #define N 50005 #define LL long long using namespace std; typedef complex<double> com; int n,m,MOD,a1,a2,a3,f[N],rev[N],g[N],p[N],len,lg; com a[N],b[N]; void fft(com *a,int f) { for (int i=0;i<len;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int i=1;i<len;i<<=1) { com wn(cos(pi/i),f*sin(pi/i)); for (int j=0;j<len;j+=(i<<1)) { com w(1,0); for (int k=0;k<i;k++) { com u=a[j+k],v=w*a[j+k+i]; a[j+k]=u+v;a[j+k+i]=u-v; w*=wn; } } } if (f==-1) for (int i=0;i<len;i++) a[i]/=len; } void solve2() { for (int i=0;i<len;i++) a[i]=p[i],b[i]=g[i]; fft(a,1);fft(b,1); for (int i=0;i<len;i++) a[i]*=b[i]; fft(a,-1); for (int i=1;i<=m;i++) p[i]=(p[i]+(int)(a[i].real()+0.1))%MOD; for (int i=0;i<len;i++) a[i]=g[i]; fft(a,1); for (int i=0;i<len;i++) a[i]*=a[i]; fft(a,-1); for (int i=1;i<=m;i++) g[i]=((int)(a[i].real()+0.1))%MOD; } void solve1() { for (int i=0;i<len;i++) a[i]=f[i],b[i]=g[i]; fft(b,1);fft(a,1); for (int i=0;i<len;i++) a[i]*=b[i]; fft(a,-1); for (int i=1;i<=m;i++) g[i]=((int)(a[i].real()+0.1))%MOD,p[i]=(p[i]+g[i])%MOD; } int main() { scanf("%d%d%d%d%d%d",&m,&MOD,&n,&a1,&a2,&a3); for (int i=1;i<=m;i++) g[i]=p[i]=f[i]=((LL)a1*i%MOD*i%MOD+(LL)a2*i%MOD+a3)%MOD; for (len=1;len<=m*2;len<<=1,lg++); for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)); int now=0,w=1; while (w*2<=n) w*=2,now++; while (now) { now--; solve2(); if (n&(1<<now)) solve1(); } printf("%d",p[m]); return 0; }