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}$自己的转移，需要解一次方程，因此需要求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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]);
}