「2026 牛客多校 3」B. 再买一瓶
https://ac.nowcoder.com/acm/contest/133878/B
一瓶饮料售价 1 元。
每次小明喝完一瓶饮料,他会以 p = \frac{a}{b} 的概率获奖。如果获奖,他将得到 c 元;否则,他什么也得不到。
他得到的钱可以用来购买更多饮料。每瓶饮料的获奖事件相互独立。小明一开始有 n 元。求他恰好喝完 m 瓶饮料后花光所有钱的概率。答案对 998244353 取模。
数据范围:1 \leq T \leq 2\times 10^5,1 \leq n, m, c \leq 2 \times 10^6,0 \leq a < b \leq 998244353。
时空限制:2s / 1024MiB。
Solution
首先可以推算出小明的中奖次数 k = \frac{m - n}{c},那么我们只需要计算出有多少种合法的中奖序列,最后再乘以 p^k(1 - p)^{m - k} 即可。
每一回合,钱数的变化量只有 -1(没有中奖)和 c - 1(中奖)两种。
从后往前考虑,那么钱数的变化量序列 a_1, \dots, a_m 满足 a_i \leq 1 且 \sum a_i = n,我们希望序列 a 的前缀和均为正数。
这恰好符合广义 Raney 引理的形式,广义 Raney 引理指出,这样的序列中的 m 个循环移位中恰好有 n 个满足前缀和均为正数。
所以合法的中奖序列个数即为 \frac{n}{m}\binom{m}{k}。
广义 Raney 引理
广义 Raney 引理:若整数序列 x_1, \dots, x_m 满足 x_i \leq 1 且 \sum_{i = 1}^m x_i = n,则它的 m 个循环移位中恰好有 n 个满足前缀和均为正数。
#include <bits/stdc++.h>
using i64 = long long;
#define debug(a) std::cout << #a << '=' << (a) << ' '
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
template <class T>
inline void chmax(T &x, const T &y) {
if (x < y) {
x = y;
}
}
const int mod = 998244353;
template <class T>
inline int norm(T x) {
x %= mod;
return x < 0 ? x + mod : x;
}
inline void add(int &x, const int &y) {
x += y; if (x >= mod) x -= mod;
}
inline void dec(int &x, const int &y) {
x -= y; if (x < 0) x += mod;
}
inline void mul(int &x, const int &y) {
x = 1ll * x * y % mod;
}
inline void neg(int &x) {
if (x) x = mod - x;
}
template <class T>
inline int qpow(int a, T b, int p) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = 1ll * ans * a % p;
a = 1ll * a * a % p;
}
return ans;
}
struct BinomCoef {
std::vector<int> fact, facv;
BinomCoef() {}
BinomCoef(int n) {
init(n);
}
void init(int n) {
fact.resize(n + 1), facv.resize(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; i ++) {
fact[i] = 1ll * fact[i - 1] * i % mod;
}
facv[n] = qpow(fact[n], mod - 2, mod);
for (int i = n - 1; i >= 0; i --) {
facv[i] = 1ll * facv[i + 1] * (i + 1) % mod;
}
}
int binom(int n, int m) {
if (n < m || m < 0) {
return 0;
}
return 1ll * facv[m] * facv[n - m] % mod * fact[n] % mod;
}
} bc(4000000);
void work() {
int n, m, c, a, b;
std::cin >> n >> m >> c >> a >> b;
if (m < n || (m - n) % c != 0) {
std::cout << 0 << '\n';
return;
}
int k = (m - n) / c;
int p = 1ll * a * qpow(b, mod - 2, mod) % mod;
int ans = 1ll * bc.binom(m, k) * n % mod * qpow(m, mod - 2, mod) % mod;
mul(ans, 1ll * qpow(p, k, mod) * qpow(mod + 1 - p, m - k, mod) % mod);
std::cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;
std::cin >> T;
while (T --) {
work();
}
return 0;
}