首先写dp方程，设f[i][j]表示第i次后第j中种1球的期望个数，所以
f[i][j]=f[i-1][j]+f[i-1][j-1]/m*1-f[i-1][j]/m*1+(1-(f[i-1][j]+f[i-1][j-1])/m)*0
->f[i][j]=f[i-1][j](1-1/m)+f[i-1][j-1]/m
矩阵加速，然后发现是循环矩阵，就只用储存第一行的信息，完事。
#include<cstdio> #include<cstring> #include<iostream> #define maxn 1021 using namespace std; int nu[maxn][maxn],n,m,k; double mat[maxn],e[maxn],ans[maxn],f[maxn],F[maxn]; int last[maxn][2]; inline int Q(int x){ if(x==0)return n;if(x==n+1)return 1; return x; } void make(){ for(int i=1;i<=n;i++)last[i][0]=i; int pos=0; for(int i=1;i<=n;i++){ pos^=1; for(int j=1;j<=n;j++){ nu[i][j]=last[j][pos^1]; last[j][pos]=last[Q(j-1)][pos^1]; } } } void mul(double a[maxn],double b[maxn],double c[maxn]){ for(int i=1;i<=n;i++)e[i]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ e[i]+=a[j]*b[nu[j][i]]; } } for(int i=1;i<=n;i++)c[i]=e[i]; } void mull(int y){ ans[1]=1; for(;y;y>>=1){ if(y&1)mul(ans,mat,ans); mul(mat,mat,mat); } } void solve(){ mat[1]=1-1.0/m;mat[n]=1.0/m; mull(k); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ F[i]+=ans[nu[i][j]]*f[j]; } } for(int i=1;i<=n;i++)printf("%.3lf\n",F[i]); } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++)scanf("%lf",f+i); make(); solve(); return 0; }