问题 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
【数据规模与约定】
对于10%的数据，N ≤ 5, M ≤ 5, K ≤ 10；
对于20%的数据，N ≤ 20, M ≤ 50, K ≤ 20；
对于30%的数据，N ≤ 100, M ≤ 100, K ≤ 100；
对于40%的数据，M ≤ 1000, K ≤ 1000；
对于100%的数据，N ≤ 1000, M ≤ 100,000,000, K ≤ 2,147,483,647。
当前状态只会由上一个点转移得到，f[i]=(m-1)/m*f[i]+1/m*f[i-1],
又因为循环的次数极大，考虑用矩阵快速幂。
优化：如果维护的矩阵每次都要全乘一遍，绝对超时，
但 1/m (m-1)/m 0
0 1/m (m-1)/m
(m-1)/m 0 1/m
可见下一排由上一排平移得到，所以只乘一排，复制下去就行
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,m;
double t[1005],a[1001][1005],b[1005];
int read()
{
int sum=0,f=1;char x=getchar();
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9')sum=sum*10+x-'0',x=getchar();
return sum*f;
}
void cheng_2()
{
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t[i]+=a[1][j]*a[j][i];
for(int i=1;i<=n;i++)
a[1][i]=t[i];
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
a[i][j]=a[i-1][j-1];
a[i][1]=a[i-1][n];
}
}
void cheng_1()
{
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
t[i]+=b[j]*a[i][j];
for(int i=1;i<=n;i++)
b[i]=t[i];
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();m=read();k=read();
for(int i=1;i<=n;i++)
b[i]=(double)read();
a[1][1]=(double)(m-1)/m;a[1][n]=(double)1/m;
for(int i=2;i<=n;i++)
a[i][i]=(double)(m-1)/m,a[i][i-1]=(double)1/m;
while(k)
{
if(k&1)cheng_1();
cheng_2();
k/=2;
}
for(int i=1;i<=n;i++)
printf("%.3lf
",b[i]);
}