题目描述

Description

有M个球，一开始每个球均有一个初始标号，标号范围为1～N且为整数，标号为i的球有ai个，并保证Σai = M。
每次操作等概率取出一个球（即取出每个球的概率均为1/M），若这个球标号为k（k < N），则将它重新标号为k + 1；若这个球标号为N，则将其重标号为1。（取出球后并不将其丢弃）
现在你需要求出，经过K次这样的操作后，每个标号的球的期望个数。

Input

第1行包含三个正整数N，M，K，表示了标号与球的个数以及操作次数。
第2行包含N个非负整数ai，表示初始标号为i的球有ai个。

Output

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

Sample Input

2 3 2
3 0

Sample Output

1.667
1.333

【样例说明】

第1次操作后，由于标号为2球个数为0，所以必然是一个标号为1的球变为标号为2的球。所以有2个标号为1的球，有1个标号为2的球。
第2次操作后，有1/3的概率标号为2的球变为标号为1的球（此时标号为1的球有3个），有2/3的概率标号为1的球变为标号为2的球（此时标号为1的球有1个），所以标号为1的球的期望个数为1/3*3+2/3*1 = 5/3。同理可求出标号为2的球期望个数为4/3。

HINT

对于100%的数据，N ≤ 1000, M ≤ 100,000,000, K ≤ 2,147,483,647。

题目分析

exm?还有循环矩阵这操作?
令 表示第i次操作 编号为j的球的期望的个数

数据范围这么大 肯定考虑矩乘啊对不对 但是这题直接矩乘肯定不过
观察转移矩阵发现，这是一个循环矩阵，而根据百度百科定理可知，循环矩阵的乘积也是循环矩阵；
而保存一个n*n的循环矩阵只需要记录第一行就可以了，乘法也就可以优化到；
exm? 还可以有这操作？

/**************************************************************
    Problem: 4204
    User: Superbia_zyb
    Language: C++
    Result: Accepted
    Time:3692 ms
    Memory:836 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
double m;
struct your
{
    double x[1010];
    your () { memset(x,0,sizeof x); };
    friend your operator*(your x,your y)
    {
        your z; 
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                z.x[(i+j)%n]+=(x.x[i]*y.x[j]);
        return z;
    }
}A,B;
void ksm(int y)
{
    while(y)
    {
        if(y&1) A=A*B;
        B=B*B,y>>=1;
    }
}
int main()
{   
    scanf("%d%lf%d",&n,&m,&k);
    for(int i=0;i<n;i++) scanf("%lf",&A.x[i]);
    B.x[0]=((m-1)/m),B.x[1]=(1/m);
    ksm(k);
    for(int i=0;i<n;i++)
        printf("%.3lf\n",A.x[i]);
    /*for(int i=1;i<=n;i++) scanf("%lf",&f[i]);
    while(k--)
    {
        for(int i=n;i>=2;i--) g[i]=(f[i]-f[i]/m+f[i-1]/m);
        g[1]=f[1]-f[1]/m+f[n]/m;
        for(int i=1;i<=n;i++) f[i]=g[i];
    }
    for(int i=1;i<=n;i++)
        printf("%.3lf\n",f[i]);*/
    return 0;
}