Slime and his nn friends are at a party. Slime has designed a game for his friends to play.
At the beginning of the game, the ii-th player has aia_i
biscuits. At each second, Slime will choose a biscuit randomly uniformly among all a1+a2++ana_1 + a_2 + \ldots + a_n biscuits, and the owner of this biscuit will give it to a random uniform player among n1n-1 players except himself. The game stops when one person will have all the biscuits.

As the host of the party, Slime wants to know the expected value of the time that the game will last, to hold the next activity on time.

For convenience, as the answer can be represented as a rational number pq\frac{p}{q}
​for coprime pp and qq , you need to find the value of (pq1)mod998244353(p \cdot q^{-1})\mod 998\,244\,353. You can prove that qmod9982443530q\mod 998\,244\,353 \neq 0

大致题意 📖

nn 个人, 第 $i 个人有 aia_i个饼干.
每次随机选择一个饼干, 将其随机分配给除了它现在所有者的其他 n1n-1 个人.
求使得一个人拥有所有饼干的期望步数, 对 998244353998244353 取模.

链接 🔗

「CF1349D」 Slime and Biscuits

题解 ❓

By Caro23333

ExE_x 为游戏结束时所有小饼干在xx手里的概率乘轮数,也就是期望
ExE_x^{'} 为如果游戏只在所有小饼干都在 xx 手里才结束时游戏的期望进行时间。
设 设PxP_x为最终游戏结束时所有小饼干在 xx 手里的概率

  1. 答案为i=1nEi\sum_{i=1}^n E_i
  2. ExE_xExE_x^{'} 不同,ExE_x 小饼干最后可在其他人手里 ,但ExE_x^{'}最后只能在xx手里
  3. sumi=1nPi=1sum_{i=1}^n P_i = 1

CC为所有饼干从ii转到jj的期望时间,这个很显然只于nn有关,于是有下列等式

Ex=Exi=1n[1x](PiC+Ei)E_x = E_x^{'} - \sum_{i=1}^n [1 \neq x] (P_i \cdot C + E_i)

移向可得

i=1nEi=ExCi=1n[1x]Pi\sum_{i=1}^n E_i = E_{x}^{'} - C \cdot \sum_{i=1}^n [1 \neq x] P_i

对等式求和得

ni=1nEi=i=1nExC(n1)i=1nPin \sum_{i=1}^n E_i = \sum_{i=1}^n E_{x}^{'} - C(n-1) \cdot \sum_{i=1}^n P_i

答案 ans=i=1nEians = \sum_{i=1}^n E_isumi=1nPi=1sum_{i=1}^n P_i = 1

nans=i=1nExC(n1)n \cdot ans = \sum_{i=1}^n E_{x}^{'} - C(n-1)

代码

const int mod = 998244353;
const double eps = 1e-8;
const int N = 3e5+10;
ll a[N],ans[N];
int main()
{
//    __IN;__OUT;
    ll n,s= 0;RLL(n);
    FOR(i,1,n) RLL(a[i]), s+=a[i];
    ll invs = fpow(s,mod-2,mod), invn = fpow(n-1,mod-2,mod);
    _FOR(i,s,1)
    {
        ll k1= i * invs % mod * invn % mod;
        ll k2= (s-i) * invs % mod;
        ans[i] = (k2 * ans[i+1] + 1) % mod * fpow(k1,mod-2,mod) % mod;
    }
    FOR(i,1,s) ans[i] = (ans[i] + ans[i-1])%mod;
    ll res = 0;
    FOR(i,1,n) res = (res + ans[s-a[i]]) % mod;
    res = (res + mod - ans[s] *(n-1) % mod) %mod;
    PLN(res*fpow(n,mod-2,mod)%mod);
    return 0;
}