张家港专业的网站制作公司,东莞市网络seo推广怎么样,网店装修模板制作,唐山 建设工程信息网站描述 这里是欢乐的进香河#xff0c;这里是欢乐的幼儿园。 今天是2月14日#xff0c;星期二。在这个特殊的日子里#xff0c;老师带着同学们欢乐地跳着#xff0c;笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息#xff0c;所有同学都安安静静… 描述 这里是欢乐的进香河这里是欢乐的幼儿园。 今天是2月14日星期二。在这个特殊的日子里老师带着同学们欢乐地跳着笑着。校长从幼儿园旁边的小吃店买了大量的零食决定分给同学们。听到这个消息所有同学都安安静静地排好了队大家都知道校长不喜欢调皮的孩子。 同学们依次排成了一列其中有A位小朋友有三个共同的欢乐系数OS和U。如果有一位小朋友得到了x个糖果那么她的欢乐程度就是f(x)Ox^2SxU。 现在校长开始分糖果了一共有M个糖果。有些小朋友可能得不到糖果对于那些得不到糖果的小朋友来说欢乐程度就是1。如果一位小朋友得不到糖果那么在她身后的小朋友们也都得不到糖果。即这一列得不到糖果的小朋友一定是最后的连续若干位 所有分糖果的方案都是等概率的。现在问题是期望情况下所有小朋友的欢乐程度的乘积是多少呆呆同学很快就有了一个思路只要知道总的方案个数T和所有方案下欢乐程度乘积的总和S就可以得到答案AnsS/T。现在他已经求出来了T的答案但是S怎么求呢他就不知道了。你能告诉他么 因为答案很大你只需要告诉他S对P取模后的结果。 后记 虽然大家都知道即便知道了T知道了S对P取模后的结果也没有办法知道期望情况下所有小朋友欢乐程度的乘积。但是当呆呆想到这一点的时候已经彻底绝望了。 格式 输入格式 第一行有2个整数分别是M和P。 第二行有一个整数A第三行有一个整数O。 第四行有一个整数S第五行有一个整数U。 输出格式 一个整数S因为答案可能很大你只需要输出S 对P取模后的结果。 看到很多大佬虐这道题我也很好奇就写了写。 题里直接给了个生成函数$c$和一个卷积的形式$c^x$,如果题里没有要求拿到糖的人是一个前缀的话直接令$c[0]1$求一发多项式快速幂就行了。 但有了限制之后考虑枚举得到糖的人数因为不能有人没有糖令$c[0]0$。 设$f[i]$表示只有i个糖时的答案最后答案为$f[m]$,则 $$f\sum_{i1}^{A}c^i$$ 感觉如果模数合适的话应该可以等比数列求和直接做吧。。。开始还以为是一道水题 但显然这道题不行那就考虑倍增。 设$g[i]c^{2^i},sumg[i]\sum_{i1}^{2^i}c^i$ 把$A$二进制拆分后用上边两个数组显然是可以求出来的懒得写了。。。 注意FFT完往回赋值时只赋$0-m$,不要把FFT完的整个数组都赋回去调了一晚上不知道哪错了。。。 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecstring5 #includecmath6 #define pi acos(-1)7 #define N 500058 #define double long double9 using namespace std;10 struct E11 {12 double x,y;13 E(){;}14 E(double _x,double _y)15 {16 x_x;y_y;17 }18 friend E operator (E a,E b)19 {20 return E(a.xb.x,a.yb.y);21 }22 friend E operator - (E a,E b)23 {24 return E(a.x-b.x,a.y-b.y);25 }26 friend E operator / (E a,double b)27 {28 return E(a.x/b,a.y/b);29 }30 friend E operator * (E a,E b)31 {32 return E(a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x);33 }34 }a[N],b[N];35 int R[N],n;36 void fft(E *a,int f)37 {38 for(int i0;in;i)if(iR[i])swap(a[i],a[R[i]]);39 for(int i1;in;i1)40 {41 E wn(cos(pi/i),f*sin(pi/i));42 for(int j0;jn;j(i1))43 {44 E w(1,0);45 for(int k0;ki;k,ww*wn)46 {47 E xa[jk],yw*a[jki];48 a[jk]xy;a[jki]x-y;49 }50 }51 }52 if(f-1)53 {54 for(int i0;in;i)a[i]a[i]/(double)n;55 }56 return ;57 }58 int m,p,A,O,S,U;59 int c[N];60 int g[15][N],sg[15][N];61 void make(int *a1,int *a2,int *a3)62 {63 for(int i0;in;i)a[i].xa[i].yb[i].xb[i].y0;64 for(int i0;in;i)a[i].xa2[i];65 for(int i0;in;i)b[i].xa3[i];66 fft(a,1);fft(b,1);67 for(int i0;in;i)a[i]a[i]*b[i];68 fft(a,-1);69 for(int i0;im;i)a1[i](int)(a[i].x0.2);70 for(int i0;im;i)a1[i]%p;71 }72 int gg[N];73 void solve()74 {75 for(int i0;in;i)g[0][i]c[i];76 for(int i1;i13;i)make(g[i],g[i-1],g[i-1]);77 for(int i0;in;i)sg[0][i]c[i];78 for(int i1;i13;i)79 {80 for(int j0;jn;j)sg[i][j]sg[i-1][j];81 make(gg,sg[i-1],g[i-1]);82 for(int j0;jn;j)83 {84 sg[i][j]sg[i][j]gg[j]; 85 if(sg[i][j]p)sg[i][j]-p;86 }87 }88 return ;89 }90 int ans[N],now[N];91 void pw(int y)92 {93 now[0]1;94 for(int i13;i0;i--)95 {96 if(y(1i))97 {98 make(gg,now,sg[i]);99 make(now,now,g[i]);
100 for(int j0;jn;j)
101 {
102 ans[j]ans[j]gg[j];
103 if(ans[j]p)ans[j]-p;
104 }
105 }
106 }
107 return ;
108 }
109 int main()
110 {
111 scanf(%d%d%d%d%d%d,m,p,A,O,S,U);
112 S%p;O%p;U%p;
113 for(int i1;im;i)c[i](1LL*O*i*i%p1LL*S*i%pU)%p;
114 n1;int l0;
115 while(n2*m)n1,l;
116 for(int i0;in;i)R[i](R[i1]1)|((i1)(l-1));
117 if(Am)Am;
118 solve();
119 pw(A);
120 printf(%d\n,ans[m]);
121 return 0;
122 } 转载于:https://www.cnblogs.com/ezyzy/p/6618613.html
