有 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();
}