[题解] Codeforces 1349 D Slime and Biscuits 概率，推式子，DP，解方程

题目

神题。很多东西都不知道是怎么凑出来的，随意设置几个变量，之间就产生了密切的关系。下次碰到这种题应该还是不会做罢。

令\(E_x\)为最后结束时所有的饼干都在第x个人手中的概率*时间的和。\(ans=\sum E_x\)。

令\(C\)为现在所有的饼干都在第x个人手中，要将它们全部转移到第y(\(x \neq y\))个人手中的期望步数。显然对于所有的x,y，C都是相同的。

令\(P_i\)为游戏结束时，所有饼干都在第i人手中的概率。

假设篡改游戏规则，饼干全在第x个人手中时游戏才结束。令此时的期望步数为\(E'_x\)。

那么就有如下等式：

\[E'_x=E_x+\sum_{i \neq x} E_i+P_iC
\]

证明就考虑\(E'_x\)的组成，第一次把所有的饼干都集中到一个人手中时，有一定的可能就是集中到了x手中，这件事的概率*期望步数是\(E_x\)；否则就要加上从这个人到x的期望步数乘上概率，是\(P_iC\)。移项并对所有x求和可得：

\[n\sum E_x=\sum E'_x -C(n-1)\sum P_i\\
n \cdot ans=\sum E'_x -C(n-1)
\]

所以求出所有\(E'_x\)和\(C\)就行了。令\(f_i\)表示需要把所有饼干都移动到某个人手中，这个人手中现在有i个饼干的还需要的步数。(反正想想转移就发现是可以这样DP的) 转移为(\(m表示\sum a_i\))：

\(f_m=0\)

\(f_0=1+\frac{n-2}{n-1}f_0+\frac{1}{n-1}f_1\)(每块饼干有n-1种走法，n-2/n-1种走到别的人手里，1/n-1种走到这个人手里)

其他：\(f_i=1+\frac{i}{m}f_{i-1}+\frac{m-i}{m}(\frac{n-2}{n-1}f_i+\frac{1}{n-1}f_{i+1})\)(先讨论动手里的还是外面的饼干)

把最后一个式子化成\(Af_{i-1}+(B-1)f_i+Cf_{i+1}+1=0\)的形式，通过推出这个式子的过程可以发现\(A+B+C=0\)(因为是三种可能性的概率和)。三个未知数不好处理，我们把f差分一下，令\(g_i=f_i-f_{i+1}\)(注意是下标小的-下标大的)。

先试试如果\(g_{i-1}\)的系数是A会怎么样。显然应该让\(f_i\)的系数=B。发现刚好得到了一个合法的式子\(Ag_{i-1}+(A+B-1)g_i+1=0\)(记得A+B+C=0)。

由第一个转移式知道\(g_0=n-1\)所以就可以递推出所有\(g_i\)，求个后缀和就是\(f_i\)，这题就做完了。时间复杂度\(O(n)\)，下面代码里写的\(O(nlogn)\)，因为懒。

#include <bits/stdc++.h>

#define rep(i,n) for(LL i=0;i<n;++i)

#define repn(i,n) for(LL i=1;i<=n;++i)

#define LL long long

#define pii pair <LL,LL>

#define fi first

#define se second

#define mpr make_pair

#define pb push_back

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)

{

	LL res=x,ret=1;

	while(a>0)

	{

		if((a&1)==1) ret=ret*res%MOD;

		a>>=1;

		res=res*res%MOD;

	}

	return ret;

}

LL n,a[100010],g[300010],m=0,f[300010];

int main()

{

  cin>>n;

  rep(i,n) scanf("%lld",&a[i]),m+=a[i];

  g[0]=n-1;

  repn(i,m-1)

  {

    LL A=i*qpow(m,MOD-2)%MOD,B=(m-i)*(n-2)%MOD*qpow(m,MOD-2)%MOD*qpow(n-1,MOD-2)%MOD;

    g[i]=(MOD+MOD-1-A*g[i-1]%MOD)*qpow((A+B-1+MOD)%MOD,MOD-2)%MOD;

  }

  f[m]=0;

  for(int i=m-1;i>=0;--i) f[i]=(f[i+1]+g[i])%MOD;

  LL ans=0;

  rep(i,n) (ans+=f[a[i]])%=MOD;

  (ans+=MOD-(n-1)*f[0]%MOD)%=MOD;

  (ans*=qpow(n,MOD-2))%=MOD;

  cout<<ans<<endl;

	return 0;

}

[题解] Codeforces 1349 D Slime and Biscuits 概率，推式子，DP，解方程的相关教程结束。