弱题（循环矩阵1）

问题 D: 弱题

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有M个球，一开始每个球均有一个初始标号，标号范围为1～N且为整数，标号为i的球有ai个，并保证Σai = M。

每次操作等概率取出一个球（即取出每个球的概率均为1/M），若这个球标号为k（k < N），则将它重新标号为k + 1；若这个球标号为N，则将其重标号为1。（取出球后并不将其丢弃）

现在你需要求出，经过K次这样的操作后，每个标号的球的期望个数。

输入

第1行包含三个正整数N，M，K，表示了标号与球的个数以及操作次数。

第2行包含N个非负整数ai，表示初始标号为i的球有ai个。

输出

应包含N行，第i行为标号为i的球的期望个数，四舍五入保留3位小数。

样例输入

2 3 2
3 0

样例输出

1.667
1.333


这道题很容易就能想到用矩阵快速幂，但n^3的时间复杂度显然是过不去，然后根据DP方程 f[i]=a/n*f[i-1]+(1-b/n)*f[i];所以每一项的转移都是从本位和前一位转移而来的，那么在构建出来的矩阵，无论自乘多少次都能地i+1行是由i行右移的得到的，最后一位到第一位；那么就可以用矩阵的第一行来表示整个矩阵，我实现的有些麻烦，我有把整个矩阵都重现了出来，其实可以直接由一个关系直接转移，还有进一步的优化空间；
  （

  1 #include<cmath>
  2 #include<ctime>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 int n,m,K;
 10 int num[1010];
 11 double f[1010];
 12 double a[1010][1010];
 13 double cc[1010];
 14 double b[1010][1010];
 15 void cheng1(){
 16     memset(cc,0,sizeof(cc));
 17     for(int i=1;i<=n;i++){
 18         for(int j=1;j<=n;j++){
 19             cc[i]+=b[j][i]*f[j];
 20         }
 21     }
 22     for(int i=1;i<=n;i++)
 23         f[i]=cc[i];
 24 }
 25 double dd[1010][1010];
 26 void cheng2(){
 27     memset(dd,0,sizeof(dd));
 28     for(int i=1;i<=n;i++){
 29         for(int j=1;j<=n;j++){
 30             dd[1][i]+=a[1][j]*a[j][i];
 31         }
 32     }
 33     for(int i=1;i<=n;i++)
 34         a[1][i]=dd[1][i];
 35     for(int i=2;i<=n;i++){
 36         for(int j=1;j<=n;j++){
 37             if(j==1){
 38                 a[i][j]=a[i-1][n];
 39                 continue;
 40             }
 41             a[i][j]=a[i-1][j-1];
 42         }
 43     }
 44 }
 45 void cheng3(){
 46     memset(dd,0,sizeof(dd));
 47     for(int i=1;i<=n;i++){
 48         for(int j=1;j<=n;j++){
 49             dd[1][i]+=a[1][j]*b[j][i];
 50             //if(i==1) cout<<"--->"<<a[1][j]<<"  "<<b[j][i]<<endl;
 51         }
 52     }
 53     for(int i=1;i<=n;i++){
 54         b[1][i]=dd[1][i];
 55     }
 56     for(int i=2;i<=n;i++){
 57         for(int j=1;j<=n;j++){
 58             if(j==1){
 59                 b[i][j]=b[i-1][n];
 60                 continue;
 61             }
 62             b[i][j]=b[i-1][j-1];
 63         }
 64     }
 65     //while(1);
 66 }
 67 int main(){
 68     //freopen("a.in","r",stdin);
 69 //  freopen("1.out","w",stdout);
 70     scanf("%d%d%d",&n,&m,&K);
 71     for(int i=1;i<=n;i++){
 72         scanf("%d",&num[i]);
 73         f[i]=num[i];
 74     }
 75     for(int i=1;i<=n;i++) b[i][i]=1;
 76     a[1][1]+=(double)(m-1)/m;
 77     a[n][1]+=(double)1/m;
 78     for(int i=2;i<=n;i++){
 79         a[i][i]+=(double)(m-1)/m;
 80         a[i-1][i]+=(double)1/m;
 81     }
 82     /*
 83     for(int i=1;i<=n;i++){
 84         for(int j=1;j<=n;j++){
 85             cout<<a[i][j]<<" ";
 86         }
 87         cout<<endl;
 88     }*/
 89     while(K){
 90         if(K&1){
 91             cheng3();
 92         }
 93         cheng2();
 94         K=K>>1;
 95     }
 96     cheng1();
 97     for(int i=1;i<=n;i++){
 98         printf("%.3lf
",f[i]);
 99     }
100     return 0;
101 }

循环矩阵留坑）