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]);
}