【题解】CF1349D SLIME AND BISCUITS 概率与期望 — dabuliuzp

有 $n$ 个人，第 $i$ 个人有 $a_i$​ 个饼干，每次随机选择一个饼干，将其随机分配给除了它现在所有者的其他 $n-1$ 个人，求使得一个人拥有所有饼干的期望步数，对 $998244353$ 取模。

$n\le 10^5 , \sum a_i\le 3\times 10^5$ 。

毒瘤题，只能说 xtq txdy ！！！

设 $E_i$ 为所有饼干在第 $i$ 个人手中的情况的期望时间那么总答案就是 $\sum\limits_{i=1}^n E_i$ 。

显然这个东西并不好求，考虑加点东西转化一下，设 $D_i$ 为所有饼干都在第 $i$ 个人手中时才结束的期望时间， $P_i$ 为所有饼干在第 $i$ 个人手中的情况的概率，此时有 $\sum P_i=1$ 。

设所有饼干从一个人全转移到另外一个人的期望时间是 $C$ ，对于任意两人，这个 $C$ 是一样的。

那么可以列出关系式：

$$D_x=E_x+\sum\limits_{i=1\&i\not=x}^{n} (E_i+P_i\times C)$$

也就是枚举第一次拿到所有饼干的人，再进行转移。

考虑将 $i\not=x$ 给消掉，将 $x=1,2,…,n$ 的式子都加起来，可以得到：

$$\sum\limits_{i=1}^n D_i=n\sum\limits_{i=1}^n E_i + C\times (n-1)\sum\limits_{i=1}^n P_i$$

由于答案是 $\sum\limits_{i=1}^n E_i$ ，所以有 $Ans=\sum\limits_{i=1}^n D_i – C(n-1)$ 。

考虑如何求出 $D_x$ 和 $C$ ，可以设一个 $f_x$ 为目前有了 $x$ 块饼干，收集到所有饼干的期望时间，显然有 $D_x=f_{a_x} , C=f_0$ 。

当 $0\le x<sum$ 时，有 $f_x=1+\frac{sum-x}{sum}(\frac{f_{x+1}}{n-1}+\frac{(n-2)f_x}{n-1})+\frac{xf_{x-1}}{sum}$ ， 显然有 $f_{sum}=0$ 。

上面的式子是判断选择的饼干，如果是他人的饼干，就有 $\frac{1}{n-1}$ 的概率给到自己， $\frac{n-2}{n-1}$ 的概率给别人，如果是自己的饼干，就一定会少掉一个。

这个消元我不太懂，但是有一个神奇的思路，就是搞一个 $f_x$ 的差分数组 $g_x=f_{x}-f_{x+1}$ ，那么有 $f_x=\sum\limits_{i=x}^{sum} g_i$ ，其中 $g_{sum}=0$ 。

那原式可以写成 $f_{x+1}\ +g_x=1+\frac{sum-x}{sum}(\frac{f_{x+1}}{n-1}+\frac{(n-2)(f_{x+1}\ +g_x)}{n-1})+\frac{x(f_{x+1}\ +g_{x}+g_{x-1}\ )}{sum}$ ，化简可得 $g_x=\frac{sum(n-1)+x(n-1)g_{x-1}}{sum-x}$ 。

那就可以 $\mathcal{O(sum)}$ 来递推出 $g_x$ 和 $f_x$ 了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int M=1e6+5,JYY=998244353;

int read(){
    int x=0,y=1;char ch=getchar();
    while(ch<'0'||ch>'9') y=(ch=='-')?-1:1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*y;
}

int n,sum=0,Ans=0,a[M],inv[M],F[M];
void solve(){
    n=read();
    for(int i=1;i<=n;i++) sum+=a[i]=read();
    inv[0]=inv[1]=1;
    for(int i=2;i<=max(sum,n);i++) inv[i]=(JYY-JYY/i)*inv[JYY%i]%JYY;
    F[0]=n-1;
    for(int i=1;i<sum;i++) F[i]=(sum*(n-1)%JYY+i*(n-1)%JYY*F[i-1]%JYY)*inv[sum-i]%JYY;
    for(int i=sum-1;i>=0;i--) F[i]=(F[i+1]+F[i])%JYY;
    for(int i=1;i<=n;i++) Ans=(Ans+F[a[i]])%JYY;
    Ans=(Ans-F[0]*(n-1)%JYY+JYY)%JYY;
    printf("%lld\n",Ans*inv[n]%JYY);
}

signed main(){
    solve();
}