弱题

发表于 | 分类于

题目

有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

OUTPUT

1.667
1.333

解题报告

弱题一点都不弱好吧= =，这题考试时打了个暴力，连不带优化的矩阵快速幂都没想出来= =
正解：
设f[i][j]表示第i个时间段，第j种的期望数量。
首先，我们可以轻松地得到一个递推式子：

f[i][j]=f[i-1][j-1]/m-f[i-1][j]+f[i-1][j]

正确性是很显然的，因为当前这个状态是由前一个转移过来，自己转移出去以及原来就有的数得到的，继续由一个高（ji）深（ben）的数学定理——乘法分配律可以得到：

f[i][j]=(m-1)/m*f[i-1][j]+f[i-1][j-1]/m

那么显然，f[i][j]只与f[i-1]时的状态有关，那么显然我们可以去掉一维,从而得到一个极其简单的递推关系，就可以用矩阵快速幂来优化啦。
我们自然可以构造出这样一个矩阵（以3*3为例）：
| (m-1)/m | 0 | 1/m |
| ————- |:————-:| —————-:|
| 1/m | (m-1)/m | 0 |
| 0 | 1/m | (m-1)/m |
但是显然普通的矩阵快速幂的复杂度是O(n³logk)，会炸，所以我们需要优化。
那么显然我们可以观察到，该矩阵的每一行，都可以由第一行平移得到，那么我们只需要维护第一行，便可推出整个矩阵，从而将复杂度将为O(能过) O(n²logk)

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
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
int n,m,k;
double a[1001][1001],b[1001];
double tmp[1001];
inline void multi_self(){
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            tmp[i]+=a[1][j]*a[j][i];
    for(int i=1;i<=n;i++)
        a[1][i]=tmp[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];
    }
}
inline void multi_ea(){
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            tmp[i]+=b[j]*a[i][j];
    for(int i=1;i<=n;i++)
        b[i]=tmp[i];
}
int main(){
//  freopen("data.in","r",stdin);
//  freopen("data.out","w",stdout);
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++){
        int x(read());
        b[i]=x*1.0;
    }
    a[1][1]=(double)(m-1)/(double)m;
    a[1][n]=1.0/(double)m;
    for(int i=2;i<=n;i++)
        a[i][i-1]=1.0/(double)m,a[i][i]=(double)(m-1)/(double)m;
    while(k){
        if(k&1)
            multi_ea();
        multi_self();
        k>>=1;
    }
    for(int i=1;i<=n;i++)
        printf("%.3lf\n",b[i]);
}

ps:写文章时，因为不会用Markdown语法加表格，活活卡了我一个小时= =