西电校赛2022F题——永久流放

题意：

有 n 个人排成一排玩游戏，拢共玩了 m 轮。一开始有一个球在第一个人手上，接下来每轮开始时，从第 1 个人到第 n 个人开始看：如果这个人手上有球，就等概率地随机扔给剩下的 n-1 个人；如果没有，就跳过。问你 m 轮结束后整个游戏传球数量的期望是多少。

$n, m\leq 1000$

不难想到如果一个人手上拿到球的概率为 p ，那么它后面的人在本轮拿到球的概率都增加 $\frac{1}{n-1}p$ ，而前面的人在下一轮拿到球的概率也增加 $\frac{1}{n-1}p$ 。

由于 n 和 m 都不大，因此可以用状态数组表示，$p[i][j]$ 表示第 i 轮第 j 个人拿到球的概率。这样就有

$p[i][j]=\sum_{k=1}^{j-1}\frac{1}{n-1}p[i][j]+\sum_{k=j+1}^{n}\frac{1}{n-1}p[i-1][j].$

当然枚举 $p[i][j]$ 已经占用 $n^2$ 复杂度了，所以暴力求和是不可以的。但是不难发现两个和式都是前缀和形式，用前缀和优化即可。

实际写的也没必要额外开一个前缀和数组，只需要用一个变量累计之前经过的人的概率，加到当前人即可求出当前人的概率。然后再从后往前遍历一边，累积从后面经过的概率，加到下一轮当前人的概率上即可。

由于球到每个人手上必然会扔出，因此每人每轮对答案的贡献就等于概率的值。即：

$ans=\sum_{i=1}^{m}\sum_{j=1}^{n}p[i][j].$

代码很简单。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mo=998244353;
int n,m;
long long p[1100][1100];
long long ans=0;
long long qcp(long long x,long long y)
{
    long long z=1;
    for(;y;y>>=1)
    {
        if(y&1)
        {
            z=z*x%mo;;
        }
        x=x*x%mo;
    }
    return z;
}
inline long long ivs(long long x)
{
    return qcp(x,mo-2);
}
void dp()
{
    p[1][1]=1;
    for(int i=1;i<=m;i++)
    {
        long long bow=0;
        for(int j=1;j<=n;j++)
        {
            p[i][j]=(p[i][j]+bow)%mo;
            bow=(bow+p[i][j]*ivs(n-1))%mo;
            ans=(ans+p[i][j])%mo;
        }
        bow=0;
        for(int j=n;j>=1;j--)
        {
            p[i+1][j]=(p[i+1][j]+bow)%mo;
            bow=(bow+p[i][j]*ivs(n-1))%mo;
        }
    }
}
int main()
{
    cin>>n>>m;
    dp();
    cout<<ans<<endl;
    return 0;
}