[题目链接]

https://codeforces.com/contest/1392/problem/H

[题解]

首先注意到抽到两次 "鬼牌" 的相邻时间间隔始终是固定的。

不妨将每次抽到一张鬼牌并重排牌序之前的抽卡流程为一次 "迭代"。 考虑一次 "迭代" 的期望轮数。

有 \(E(x) = \frac{n}{n + m} + 2 \cdot \frac{n}{n + m} \cdot \frac{m}{n + m - 1} + 3 \cdot \frac{n}{n + m} \cdot \frac{n - 1}{n + m - 1} \cdot \frac{m}{n + m - 2} + ... + = \sum_{i}{i * \frac{m}{n + m + 1 - i} \prod_{j}{\frac{n - j}{n + m - j}}}\)。

令 \(w_{k} = \prod_{j=0}^{k - 2}{\frac{n - j}{n + m - j}}\) , 可以通过递推的方式在 \(O(NlogN)\) 时间内求解 \(E(x)\)。

接着考虑期望需要多少轮迭代才能抽到所有的牌。

不妨设 \(f_{k}\) 表示还有 \(k\) 张不在牌堆里的牌期望轮数。

那么有 \(\frac{m}{m + k}\) 的概率抽到 \(Joker\) , 从而结束一轮迭代。

另有 \(\frac{k}{m + k}\) 的概率抽到一张需要的牌 ， 转化为 \((k - 1)\) 的子问题。

也就是说 \(f_{k} = \frac{m}{m + k}(f_{k} + 1) + \frac{k}{m + k}f_{k - 1}\)。

解得 \(f_{k} = f_{k - 1} + \frac{m}{k}\)。

也就是说 \(f_{n} = f_{1} + \sum_{i = 2}^{n}{\frac{m}{i}}\)。

\(f_{1}\) 显然为 \(\frac{1}{\frac{1}{m + 1}} = m + 1\) ， 于是 \(f_{n} = 1 + m\sum_{i = 1}^{n}{\frac{1}{i}}\)。

至此我们成功地在线性时间内求解了 \(f\)。

答案显然为 \(E(x)f(n)\)。 这样就可以做到 \(O(NlogN)\) 的优秀复杂度了。

但事实上 \(E(x)\) 可以不通过递推得到 ， 考虑期望的线性性 ， 在一轮迭代中 ， 每张数字牌都有 \(\frac{1}{m + 1}\) 的概率被抽出 ， 概率相加就是期望(还要加上 \(1\) , 表示最终摸到一张 \(Joker\))。

故 \(E(x) = \frac{n}{m + 1} + 1\)。

这样做时间复杂度为 \(O(N)\) (瓶颈在于线性求逆元)。

[代码]

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
#define rep(i , l , r) for (int i = (l); i < (r); ++i)
 
const int mod = 998244353;
 
int N , M;
 
inline void inc(int &x , int y) {
	x = x + y < mod ? x + y : x + y - mod;
}
inline int qPow(int a , int b) {
	int c = 1;
	for (; b; b >>= 1 , a = 1LL * a * a % mod) if (b & 1) c = 1LL * c * a % mod;
	return c;
}
 
int main() {
	
	 scanf("%d%d" , &N , &M); 
	 int ans = 1LL * (N + M + 1) * qPow(M + 1 , mod - 2) % mod;
	 int ex = 0;
	 for (int i = 1; i <= N; ++i) inc(ex , qPow(i , mod - 2));
	 ex = (1ll * ex * M % mod + 1) % mod;
	 printf("%d\n" , 1ll * ans * ex % mod);
     return 0;
}