[题目链接]
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 + msum_{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
" , 1ll * ans * ex % mod);
return 0;
}