ZS Shuffles Cards 题解
我们把每一次抽一些数字牌再抽到 joker 视作一局游戏。
每局期望轮数
首先考虑 \(f_i\) 表示每一局游戏抽出 \(i\) 张牌的概率。
那么就是先抽出 \(i - 1\) 张数字牌，再抽出一张 joker 。
概率就是 ：
\[f_i = \frac m {n + m - i +1}\prod_{k = 0} ^ {i - 2} \frac {n - k}{m + n - k} \]一局游戏期望抽牌（轮）数量也就是：
\[\begin{aligned} E &= \sum_{i = 1}^{n + 1} i \times f_i\\ &= \sum_{i = 1}^{n + 1} i \times \frac m {n + m - i +1}\prod_{k = 0} ^ {i - 2} \frac {n - k}{m + n - k}\\ \end{aligned} \]直接算这个式子会超时，我们可以先预处理后面的部分：
令
\[g_i = \prod_{k = 0} ^ {i - 2} \frac {n - k}{m + n - k} \]可得
\[g_{i + 1} = g_i * \frac{n-i+1}{m + n - i + 1} \]就转化成
\[E = \sum_{i = 1}^{n + 1} i \times \frac m {n + m - i +1}\times g_{i+1}\\ \]期望局数
令 \(h_i\) 表示集合 \(S\) 内还缺 \(i\) 个数才凑够 \(n\) 时，期望再玩多少局。
显然答案就是 \(h_n\)。
若抽到了缺少的牌，那么就是：
\(\frac k {m + k} f_{k-1}\)
若抽到鬼牌，那么就是（加 1 是因为新的一局）：
\(\frac m {m + k} {f_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_0 = 1\) 。
因为即使你的集合内的数已经凑够了，你也要抽到 joker 才能停止。
最后答案就是
\[ans = E \times f_n \]温馨提示
建议预处理逆元（我最开始没有预处理虽然本地没超时但测评会T）
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
const int N = 4e6 + 10;
ll n, m, w[N], ans1 = 0, ans2 = 0;
ll pr[N], ip[N], rv[N];
inline ll mpow(ll x, ll k){
ll ans = 1;
while(k){
if(k & 1) ans = ans * x % mod;
k >>= 1;
x = x * x % mod;
}
return ans;
}
void pre(int n){
pr[0] = 1;
for(int i = 1; i <= n; ++i) pr[i] = pr[i - 1] * i % mod;
ip[n] = mpow(pr[n], mod - 2);
for(int i = n - 1; i >= 1; --i) ip[i] = ip[i + 1] * (i + 1) % mod;
for(int i = 1; i <= n; ++i) rv[i] = ip[i] * pr[i - 1] % mod;
}
void op(){
w[1] = 1;
for(int i = 1; i <= n + 1; ++i){
w[i + 1] = w[i] * (n - i + 1) % mod * rv[n + m - i + 1] % mod;
ans1 = (ans1 + i * m % mod * rv[n + m - i + 1] % mod * w[i] % mod) % mod;
}
ans2 = m + 1;
for(int i = 2; i <= n; ++i){
ans2 = (ans2 + m * rv[i] % mod) % mod;
}
}
int main(){
cin>> n >> m;
pre(n + m + 1);
op();
cout<<ans1 * ans2 % mod;
return 0;
}