CF1392H - ZS Shuffles Cards

题目大意

给定\(n\)张卡和\(m\)个终止符，初始时随机打乱成排列，每次操作选出最前面的卡\(x\)拿走

1.如果\(x\)不是终止符，将\(x\)放入集合

2.如果\(x\)是终止符，那么重新打乱\(n+m\)张卡

求期望多少步\(S\)变成全集

分析

令\(dp_i\)表示当前手上有\(i\)张不同卡时期望多少步结束

按轮考虑，一轮期望操作次数固定，即

\(\displaystyle \frac{\displaystyle \sum _{i=0}^n \binom{n+m-i-1}{m-1}(i+1)}{\displaystyle \binom{n+m}{m}}\)

现在考虑从\(dp_{i+j}\)转移过来，当前的牌可以分为三类

1.手里有的

2.手里没有的

3.终止牌

我们计算\(dp_{i+j}\)向\(dp_i\)转移时的概率，并不需要管1类卡，只需要考虑2,3类卡的相对顺序

不妨直接忽略手里的\(i\)张卡，得到转移系数

\(dp_{i+j}\rightarrow dp_i: \cfrac{\displaystyle \binom{n-i-j-1}{m-1}}{\displaystyle \binom{n-i+m}{m}}\)

容易发现可以将\(\displaystyle dp_{i+j}\binom{n-i-j-1}{m-1}\)累和完成

注意\(dp_i\)有向\(dp_{i}\)自己的转移，需要解一次方程，因此需要求逆元

const int N=4e6+10,P=998244353;

int n,m;
int I[N],J[N];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int F[N];
ll C(int n,int m){ return 1ll*J[n]*I[m]%P*I[n-m]%P; }
ll IC(int n,int m){ return 1ll*I[n]*J[m]%P*J[n-m]%P; }

int main(){
	rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P; 
	n=rd(),m=rd();
	ll s=0,inv=IC(n+m,m),coef=0;
	rep(i,0,n) coef=(coef+C(n+m-i-1,m-1)*(i+1))%P;
	coef=coef*inv%P;

	drep(i,n-1,0) {
		ll p=C(n+m-i-1,m-1),t=IC(n-i+m,m);
		F[i]=(s*t%P+coef)%P*qpow(P+1-p*t%P)%P;
		s=(s+1ll*p*F[i])%P;
	}
	printf("%d\n",F[0]);
}