Solution -「CF 1392H」ZS Shuffles Cards

(mathcal{Description})

打乱的 (n) 张编号 (1sim n) 的数字排和 (m) 张鬼牌。随机抽牌，若抽到数字，将数字加入集合 (S)；否则，还原牌堆（但不清空 (S)）。若 (S=[1,n]) 且抽到鬼牌时结束抽牌。求期望抽牌次数。

(n,mle2 imes10^6)。

(mathcal{Solution})

称从初始牌堆开始抽牌一直到抽到鬼牌为一轮操作，发现结束时必然抽了若干个完整的轮且不能中途终止。所以“抽完一轮”和“结束抽牌”两事件独立，分别记二者的随机变量为 (xi_1) 和 (xi_2)，则答案为 (E(xi_1xi_2)=E(xi_1)E(xi_2))。

(E(xi_1)) 显然等于一轮抽到数字牌的期望张数 (+1)。而由期望线性性，它也等于 (n imes p+1)，其中 (p) 表示抽到某一张牌的概率，有：

[p=frac{1}{m+1} ]

一种直观的解释方法是，把每张数字牌和 (m) 张鬼牌绑为一组，每次拿出这样一组牌，再从中随机选出一张作为抽到的牌，其它牌丢掉，不难证明这和原操作等价。显然拿出某一张数字牌所在的组时，有 (p=frac{1}{m+1}) 的概率真正拿到这张数字牌，不然就永远拿不到了。于是，我们求到了：

[E(xi_1)=frac{n}{m+1}+1 ]

求 (E(xi_2))，令 (f(i)) 表示已有 (|S|=n-i)，到结束时的期望轮数。方程有：

[f(i)=frac{m}{m+i}left(f(i)+1 ight)+frac{i}{m+i}f(i-1) ]

特别留意上式，总牌数 (m+i) 是因为其他 (n-i) 张数字牌没有任何意义，可以忽略；前一项抽到鬼牌，轮数才要 (+1)；后一项抽到有用数字牌，但是这一轮并没有结束，所以不用 (+1)。

整理一下：

[f(i)=f(i-1)+frac{m}{i} ]

对于边界 (f(1))，即 (m+1) 张里挑出一张的期望，显然有 (f(1)=m+1)。代一代求出 (f(n))：

[f(n)=1+msum_{i=1}^nfrac1{i} ]

综上，答案为：

[egin{aligned} E(xi_1xi_2)&=E(xi_1)E(xi_2)\ &=left(frac{n}{m+1}+1 ight)f(n)\ &=left( frac{n}{m+1}+1 ight)left( 1+msum_{i=1}^nfrac1i ight) end{aligned} ]

计算即可。复杂度 (mathcal O(n+log m))。

(mathcal{Code})

/* Clearink */

#include <cstdio>

const int MOD = 998244353, MAXN = 2e6;
int n, m, inv[MAXN + 5];

inline int qkpow ( int a, int b, const int p = MOD ) {
	int ret = 1;
	for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;
	return ret;
}

int main () {
	scanf ( "%d %d", &n, &m );
	int turn = ( n + m + 1ll ) * qkpow ( m + 1, MOD - 2 ) % MOD, times = 1;
	for ( int i = 1; i <= n; ++ i ) {
		inv[i] = i ^ 1 ? 1ll * inv[MOD % i] * ( MOD - MOD / i ) % MOD : 1;
		times = ( times + 1ll * m * inv[i] ) % MOD;
	}
	printf ( "%d
", int ( 1ll * turn * times % MOD ) );
	return 0;
}