BZOJ4204: 取球游戏

题解:

(我这个大傻叉连这题都不会做了)

首先肯定是转移了...

我们单独考虑每个球,变化的概率都是$\frac{1}{m}$.

于是令$f_i$表示编号为$i$的球的个数,考虑一次操作$f_i$的变化.

考虑单个标号为$i$的球对$f_i$的影响:$\frac{1}{m}\times{0}+(1-\frac{1}{m})\times{1}$

考虑单个标号为$i-1$的球对$f_i$的影响:$\frac{1}{m}\times{1}+(1-\frac{1}{m})\times{0}$

然后我们就搞出了转移矩阵.

有意思的是,这是一个循环矩阵!

也就是说,从第二行开始,每一行都是上一行右移一位得到的.

显而易见,循环矩阵的乘积依然是循环矩阵.

所以我们只要暴力算出第一行就行了,所以可以$O(n^2)$暴力,也可以利用FFT优化至$O(nlogn)$.

这样的话就能做这道题目了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 1010
int n,m,k,a[N];
struct Vector{
    f2 line[N],row[N];
    inline void operator*=(const Vector&B){
        static f2 _line[N];
        int i,j,k;
        for(i=0;i<n;++i)
            _line[i]=0;
        for(i=0;i<n;++i)
            for(j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
                _line[i]+=line[k]*B.row[j];
        for(i=0;i<n;++i)
            line[i]=_line[i];
        for(i=0;i<n;++i)
            row[(n-i)%n]=line[i];
    }
}t,re;
int main(){
    cin>>n>>m>>k;
    int i,j;
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);
    re.line[0]=re.row[0]=1;
    t.line[0]=(f2)(m-1)/m;
    t.line[1]=1.0/m;
    t.row[0]=(f2)(m-1)/m;
    t.row[n-1]=1.0/m;
    for(;k;k>>=1,t*=t)
        if(k&1)
            re*=t;
     
    f2 ans;
    for(i=0;i<n;++i){
        for(ans=0,j=(n-i)%n,k=0;k<n;++k,(++j)%=n)
            ans+=a[k]*re.row[j];
        printf("%.3lf\n",ans);
    }
    return 0;
}