bzoj4332 JSOI2012 分零食

NO IMAGE

Description


這裡是歡樂的進香河,這裡是歡樂的幼兒園。
今天是2月14日,星期二。在這個特殊的日子裡,老師帶著同學們歡樂地跳著,笑著。校長從幼兒園旁邊的小吃店買了大量的零食決定分給同學們。聽到這個訊息,所有同學都安安靜靜地排好了隊,大家都知道,校長不喜歡調皮的孩子。
同學們依次排成了一列,其中有A位小朋友,有三個共同的歡樂係數O,S和U。如果有一位小朋友得到了x個糖果,那麼她的歡樂程度就是f(x)=O*x2 S*x U。
現在校長開始分糖果了,一共有M個糖果。有些小朋友可能得不到糖果,對於那些得不到糖果的小朋友來說,歡樂程度就是1。如果一位小朋友得不到糖果,那麼在她身後的小朋友們也都得不到糖果。(即這一列得不到糖果的小朋友一定是最後的連續若干位)
所有分糖果的方案都是等概率的。現在問題是:期望情況下,所有小朋友的歡樂程度的乘積是多少?呆呆同學很快就有了一個思路,只要知道總的方案個數T和所有方案下歡樂程度乘積的總和S,就可以得到答案Ans=S/T。現在他已經求出來了T的答案,但是S怎麼求呢?他就不知道了。你能告訴他麼?
因為答案很大,你只需要告訴他S對P取模後的結果。
後記:
雖然大家都知道,即便知道了T,知道了S對P取模後的結果,也沒有辦法知道期望情況下,所有小朋友歡樂程度的乘積。但是,當呆呆想到這一點的時候,已經徹底絕望了。

對於100%的資料,M<=10000,P<=255,A<=108,O<=4,S<=300,U<=100。

Solution


設f[i,j]表示前i個人分j顆糖的答案,那麼f[i,j]=∑k=1j−1f[i−1,j−k]∗g[k]” role=”presentation”>f[i,j]=∑j−1k=1f[i−1,j−k]∗g[k]f[i,j]=∑k=1j−1f[i−1,j−k]∗g[k]f[i,j]=\sum_{k=1}^{j-1}f[i-1,j-k]*g[k]
這是個卷積,其中g[x]=Ox2 Sx U” role=”presentation”>g[x]=Ox2 Sx Ug[x]=Ox2 Sx Ug[x]=Ox^2 Sx U
看起來好像快速冪一下答案就出來了,但是題目要求恰好m個的答案,那麼再設一個p[n,m]=∑i=1nf[i][m]” role=”presentation”>p[n,m]=∑ni=1f[i][m]p[n,m]=∑i=1nf[i][m]p[n,m]=\sum_{i=1}^{n}f[i][m]
p[n,m]=∑i=1nf[i][m]=p[n2][m] ∑i=1n2f[i n2][m]” role=”presentation”>p[n,m]=∑ni=1f[i][m]=p[n2][m] ∑n2i=1f[i n2][m]p[n,m]=∑i=1nf[i][m]=p[n2][m] ∑i=1n2f[i n2][m]p[n,m]=\sum_{i=1}^{n}f[i][m]=p[\frac{n}{2}][m] \sum_{i=1}^{\frac{n}{2}}f[i \frac{n}{2}][m]
            =∑i=1np[n2][m] ∑i=1n2∑j=1m−1f[i][j]∗f[n2][m−j]” role=”presentation”>            =∑ni=1p[n2][m] ∑n2i=1∑m−1j=1f[i][j]∗f[n2][m−j]            =∑i=1np[n2][m] ∑i=1n2∑j=1m−1f[i][j]∗f[n2][m−j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{i=1}^{\frac{n}{2}}\sum_{j=1}^{m-1}f[i][j]*f[\frac{n}{2}][m-j]
            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗∑i=1n2f[i][j]” role=”presentation”>            =∑ni=1p[n2][m] ∑m−1j=1f[n2][m−j]∗∑n2i=1f[i][j]            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗∑i=1n2f[i][j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{j=1}^{m-1}f[\frac{n}{2}][m-j]*\sum_{i=1}^{\frac{n}{2}}f[i][j]
            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗p[n2][j]” role=”presentation”>            =∑ni=1p[n2][m] ∑m−1j=1f[n2][m−j]∗p[n2][j]            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗p[n2][j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{j=1}^{m-1}f[\frac{n}{2}][m-j]*p[\frac{n}{2}][j]
可以發現後面那部分又是一個卷積,那麼遞迴求就ok

終於打了一波蝴蝶變換,感覺還行

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <complex>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
typedef std:: complex <double> com;
const double pi=acos(-1);
const double eps=0.1;
const int N=50005;
com a[N],b[N],c[N];
int g[N],f[N],p[N];
int rev[N],len,lg,MOD;
int A,B,C,n,m;
void FFT(com *a,int f) {
for (int i=0;i<len;i  ) if (i<rev[i]) std:: swap(a[i],a[rev[i]]);
for (int i=1;i<len;i<<=1) {
com wn(cos(pi/(double)i),(double)f*sin(pi/(double)i));
for (int j=0;j<len;j =i*2) {
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 solve1() {
rep(i,0,len-1) a[i]=f[i];
rep(i,0,len-1) b[i]=g[i];
FFT(a,1); FFT(b,1);
rep(i,0,len-1) c[i]=a[i]*b[i];
FFT(c,-1);
rep(i,1,m) f[i]=(int)(c[i].real() eps)%MOD,p[i]=(p[i] f[i])%MOD;
}
void solve2() {
rep(i,0,len-1) a[i]=f[i];
rep(i,0,len-1) b[i]=p[i];
FFT(a,1); FFT(b,1);
rep(i,0,len-1) c[i]=a[i]*b[i];
FFT(c,-1);
rep(i,1,m) p[i]=(p[i] (int)(c[i].real() eps)%MOD)%MOD;
rep(i,0,len-1) c[i]=a[i]*a[i];
FFT(c,-1);
rep(i,1,m) f[i]=(int)(c[i].real() eps)%MOD;
}
int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
scanf("%d%d%d",&m,&MOD,&n);
scanf("%d%d%d",&A,&B,&C);
for (len=1,lg=0;len<=m*2;len*=2,lg  );
for (int i=0;i<len;i  ) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
rep(i,1,m) p[i]=g[i]=f[i]=(A%MOD*i%MOD*i%MOD B*i%MOD C)%MOD;
int now=0,w=1; n=tmp;
while (w*2<=n) w*=2,now  ;
while (now--) {
solve2();
if (n&(1<<now)) solve1();
}
printf("%d\n", p[m]);
return 0;
}