首页 > 代码库 > bzoj2510: 弱题
bzoj2510: 弱题
求k时刻一个标号转移到各位置的概率，最后枚举每个标号加权求期望。可以发现转移矩阵是循环矩阵，因此乘法是n^2的。另外这个乘法是圆周卷积的形式，然后就作死写了发fft，发现精度升天了= =
#include<cstdio>#include<cstring>#define N 1000int n,m,k,i,j;typedef double ds[N];ds s,t,u,q;void mul(double* s,double* t){ memset(u,0,n*8); for(i=0;i!=n;++i) for(j=0;j!=n;++j) u[(i+j)%n]+=s[i]*t[j]; memcpy(s,u,n*8);}int main(){ scanf("%d%d%d",&n,&m,&k); for(i=0;i!=n;++i) scanf("%lf",t+i); *q=1-1./m; q[1]=1./m; for(*s=1;k;k/=2){ if(k%2)mul(s,q); if(k/2)mul(q,q); else mul(t,s); } for(i=0;i!=n;++i) printf("%.3f\n",t[i]);}
bzoj2510: 弱题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。