本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 11:32:08

[ABC360E] Random Swaps of Balls

题目考查：期望，逆元。
题目简述：
给你一个数 $n$，有 $n-1$ 个白球和 $1$ 个黑球，黑球一开始在最左侧。有 $k$ 次操作，每次操作等概率随机地从区间 $[1,n]$ 选出两个数 $a,b$，交换处于从左往右数第 $a$ 个球和第 $b$ 个球，求最后黑球所在位置的期望值对 $998244353$ 取模的结果。
数据范围：

• $1\le n<998244353$
• $1\le k\le 10^5$

很容易发现除了黑球在第一个位置外，黑球在其他位置上的概率是相同的。
那么我们设第 $i$ 次操作后黑球在第一个位置上的概率（当然要对 $998244353$ 取模，下同）为 $f_i$，在其他位置上的概率为 $g_i$。

注：
$\displaystyle(\frac{a}{b}+\frac{c}{d})\bmod p$ 和 $\displaystyle(\frac{a}{b}\bmod p+\frac{c}{d}\bmod p)\bmod p$ 是相同的，下面给出证明：
$$\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)$。
代码：

#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;
}