[ABC360E] Random Swaps of Balls 讲解
zrl123456
·
·
题解
[ABC360E] Random Swaps of Balls
题目考查：期望，逆元。
题目简述：
给你一个数 n，有 n-1 个白球和 1 个黑球，黑球一开始在最左侧。有 k 次操作，每次操作等概率随机地从区间 [1,n] 选出两个数 a,b，交换处于从左往右数第 a 个球和第 b 个球，求最后黑球所在位置的期望值对 998244353 取模的结果。
数据范围：
注：
$$\begin{aligned}(\frac{a}{b}+\frac{c}{d})\bmod p&=\frac{ad+bc}{bd}\bmod p\\&=(ad+bc)(bd)^{-1}\bmod p\end{aligned}$$
根据费马小定理（$a^p\equiv a\pmod p$，$p\in \text{prime}$），得：
$$\begin{aligned}(\frac{a}{b}+\frac{c}{d})\bmod p&=(ad+bc)(bd)^{-1}\bmod p\\&=(ad+bc)(bd)^{p-2}\bmod p\end{aligned}$$
而：
$$\begin{aligned}(\frac{a}{b}\bmod p+\frac{c}{d}\bmod p)\bmod p&=(ab^{-1}+cd^{-1})\bmod p\\&=(ab^{p-2}+cd^{p-2})\bmod p\end{aligned}$$
我们将 $(ad+bc)(bd)^{p-2}$ 转化：
$$\begin{aligned}(ad+bc)(bd)^{p-2}&=ad(bd)^{p-2}+bc(bd)^{p-2}\\&=ab^{p-2}d^{p-1}+cd^{p-2}b^{p-1}\\&=ab^{p-2}+cd^{p-2}\end{aligned}$$
证毕。
减法，乘法同理。
接下来对 $f_i$ 考虑转移方程，想要将黑球移到其他地方，有 $(1,2),(1,3),\dots,(1,n-1),(1,n)$ 和 $(2,1),(3,1),\dots,(n-1,1),(n,1)$ 这些 $2(n-1)$ 种方法，那么黑球留在原地就有 $n^2-2(n-1)$ 种方法，得转移方程：
$$f_i=((n^2-2(n-1))f_{i-1}+2(n-1)g_{i-1})\bmod 998244353$$
然后对 $g_i$ 考虑转移方程，想要将黑球移到最左边，只有 $2$ 种方法。那么留在除了最左边的其他地方有 $n^2-2$ 种方法，得转移方程：
$$g_i=((n^2-2)g_{i-1}+2f_{i-1})\bmod 998244353$$
最后答案就是：
$$ans=(f_k+(n(n+1)-1)g_k)\bmod 998244353$$
总体复杂度为 $\Theta(k)$。
代码：
```cpp
#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int>
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
using namespace std;
const int N=1e5+5,MOD=998244353;
int f[N],g[N];
inl int ksm(int a,int b){
reg int num=a%MOD,ans=1;
while(b){
if(b&1) (ans*=num)%=MOD;
(num*=num)%=MOD;
b>>=1;
}
return ans;
}
inl int inv(int a,int b){
return a*ksm(b,MOD-2)%MOD;
}
signed main(){
fst;
reg int n,k,p,q,r,s;
cin>>n>>k;
p=inv((n-1<<1)%MOD,n*n%MOD);
q=inv(2,n*n%MOD);
r=inv((n*n-(n-1<<1))%MOD,n*n%MOD);
s=inv((n*n-2)%MOD,n*n%MOD);
f[0]=1;
g[0]=0;
rep(i,1,k){
f[i]=(f[i-1]*r%MOD+g[i-1]*p%MOD)%MOD;
g[i]=(g[i-1]*s%MOD+f[i-1]*q%MOD)%MOD;
}
cout<<(f[k]+((n*(n+1)>>1)-1)%MOD*g[k]%MOD)%MOD;
return 0;
}
```