Codeforces Round #641 Div1.D Slime and Biscuits 中文题解
Caro23333
2020-04-30 00:30:44
### Slime and Biscuits 中文题解
设 $E_x$ 为在所有游戏结束时所有小饼干在 $x$ 手里的情况,概率乘时间的和(注意此时所有情况的概率加起来并不是 $1$ ,所有 $E_i$ 中概率的和才是 $1$ )。则答案即为 $\sum\limits_{i=1}^n E_i$。
设 $E'_x$ 为如果游戏只在所有小饼干都在 $x$ 手里才结束时游戏的期望进行时间。
设 $P_x$ 为最终游戏结束时所有小饼干在 $x$ 手里的概率,即 $E_x$ 这一部分对应的总概率。不难发现$\sum\limits_{i=1}^n P_i = 1$。
再设常数$C$表示所有小饼干从 $i$ 手里转移到 $j$ 手里的期望时间(此时游戏结束条件是全集中在 $j$ 手里,与 $E'_j$ 的结束条件相同,且 $C$ 的值对所有 $i,j$ 均相等),则不难发现我们有恒等式:
$$E_x = E'_x-\sum\limits_{i=1}^n[i\neq x]( P_i\cdot C+E_i)$$
这个等式即为考虑 $E'_x$ 中的所有情况中游戏分别在最后饼干在谁手里时结束。
将等式移项可得 :
$$\sum\limits_{i=1}^n E_i=E'_x-C\cdot \sum\limits_{i=1}^n[i\neq x]P_i$$
将等式对 $x=1,2,\cdots,n$ 求和,可以得到 :
$$n\sum\limits_{i=1}^nE_i=\sum\limits_{i=1}^nE'_i-C(n-1)\sum\limits_{i=1}^nP_i$$
注意到 $ans=\sum\limits_{i=1}^nE_i$ 且 $\sum\limits_{i=1}^nP_i=1$ ,则得出:
$$n\cdot ans=\sum\limits_{i=1}^nE'_i-C(n-1)$$
在求 $E'_x$ 和 $C$ 时我们可以注意到只关心所有饼干是否在目标人手中,所以设 $f_m$ 为此时有 $m$ 个小饼干在目标人手中时最后全到目标人手中的期望时间,则不难得到 $f_m,f_{m+1},f_{m-1}$ 的等式关系:
$$
f_m = \left\{
\begin{array}{lcl}
1 + \frac{(\sum a_i) - m}{\sum a_i}\left(\frac{1}{n-1}f_{m+1} + \frac{n-2}{n-1}f_m\right) + \frac{m}{\sum a_i}f_{m-1} & 0<m<\sum a_i \\
1 + \frac{1}{n-1}f_{m+1} + \frac{n-2}{n-1}f_m & m=0 \\
0 & m=\sum a_i \\
\end{array} \right.
$$
不难在 $O(\sum\limits_{i=1}^na_i)$ 时间内,通过消元的方法求出所有 $f_n$ ,从而求出 $E'_x$ 和 $C$ ,得出答案。
总复杂度为 $O(n+\sum\limits_{i=1}^na_i)$ 。
P.S. 事实上,这种做法可能在消元过程中出现除以 $0$ 的情况,所以我们安排了一组 hack 数据。另一种更为妥帖的做法是,将 $g_i = f_i - f_{i+1}$ 设为未知数列方程求解,可以证明不会出现问题。标程中使用了这种做法。这种做法由 Elegia 提供。
Problem and Tutorial by he_____he
```cpp
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int cys=998244353;
int n,m;
ll a[100005],ans[300005];
ll qpow(ll x,ll p){
ll ret=1;
for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
return ret;
}
int main(){
n=readint();
for(int i=1;i<=n;i++) a[i]=readint(),m+=a[i];
ll invm=qpow(m,cys-2),invn1=qpow(n-1,cys-2);
for(int i=m;i>=1;i--){
ll k1=i*invm%cys*invn1%cys,k2=(m-i)*invm%cys;
ans[i]=(k2*ans[i+1]+1)%cys*qpow(k1,cys-2)%cys;
}
for(int i=1;i<=m;i++) ans[i]=(ans[i]+ans[i-1])%cys;
ll res=0;
for(int i=1;i<=n;i++) res=(res+ans[m-a[i]])%cys;
res=(res+cys-ans[m]*(n-1)%cys)%cys;
printf("%lld\n",res*qpow(n,cys-2)%cys);
return 0;
}
```