题解:
(我这个大傻叉连这题都不会做了
)
首先肯定是转移了...
我们单独考虑每个球,变化的概率都是1m.
于是令fi表示编号为i的球的个数,考虑一次操作fi的变化.
考虑单个标号为i的球对fi的影响:1m×0+(1−1m)×1
考虑单个标号为i−1的球对fi的影响:1m×1+(1−1m)×0
然后我们就搞出了转移矩阵.
有意思的是,这是一个循环矩阵!
也就是说,从第二行开始,每一行都是上一行右移一位得到的.
显而易见,循环矩阵的乘积依然是循环矩阵.
所以我们只要暴力算出第一行就行了,所以可以O(n2)暴力,也可以利用FFT优化至O(nlogn).
这样的话就能做这道题目了.
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include<cstdio>#include<cctype>#include<cstring>#include<iostream>#include<algorithm>using namespace std; typedef double f2; #define N 1010int n,m,k,a[N];struct Vector{ f2 line[N],row[N]; inline void operator*=(const Vector&B){ static f2 _line[N]; int i,j,k; for(i=0;i<n;++i) _line[i]=0; for(i=0;i<n;++i) for(j=(n-i)%n,k=0;k<n;++k,(++j)%=n) _line[i]+=line[k]*B.row[j]; for(i=0;i<n;++i) line[i]=_line[i]; for(i=0;i<n;++i) row[(n-i)%n]=line[i]; }}t,re;int main(){ cin>>n>>m>>k; int i,j; for(i=0;i<n;++i) scanf("%d",&a[i]); re.line[0]=re.row[0]=1; t.line[0]=(f2)(m-1)/m; t.line[1]=1.0/m; t.row[0]=(f2)(m-1)/m; t.row[n-1]=1.0/m; for(;k;k>>=1,t*=t) if(k&1) re*=t; f2 ans; for(i=0;i<n;++i){ for(ans=0,j=(n-i)%n,k=0;k<n;++k,(++j)%=n) ans+=a[k]*re.row[j]; printf("%.3lf\n",ans); } return 0;} |