「2026 牛客多校 3」B. 再买一瓶

发表于 分类于 本文字数： 924 阅读时长 ≈ 1 分钟

Description

Link：https://ac.nowcoder.com/acm/contest/133878/B

一瓶饮料售价 11 元。

每次小明喝完一瓶饮料，他会以 p=abp = \frac{a}{b} 的概率获奖。如果获奖，他将得到 cc 元；否则，他什么也得不到。

他得到的钱可以用来购买更多饮料。每瓶饮料的获奖事件相互独立。小明一开始有 nn 元。求他恰好喝完 mm 瓶饮料后花光所有钱的概率。答案对 998244353998244353 取模。

数据范围：1≤T≤2×1051 \leq T \leq 2\times 10^5，1≤n,m,c≤2×1061 \leq n, m, c \leq 2 \times 10^6，0≤a<b≤9982443530 \leq a < b \leq 998244353。

时空限制：22s / 10241024MiB

Solution

首先可以推算出小明的中奖次数 k=m−nck = \frac{m - n}{c}，那么我们只需要计算出有多少种合法的中奖序列，最后再乘以 pk(1−p)m−kp^k(1 - p)^{m - k} 即可。

每一回合，钱数的变化量只有 −1-1（没有中奖）和 c−1c - 1（中奖）两种。

从后往前考虑，那么钱数的变化量序列 a1,…,ama_1, \dots, a_m 满足 ai≤1a_i \leq 1 且 ∑ai=n\sum a_i = n，我们希望序列 aa 的前缀和均为正数。

这恰好符合广义 Raney 引理的形式，广义 Raney 引理指出，这样的序列中的 mm 个循环移位中恰好有 nn 个满足前缀和均为正数。

所以合法的中奖序列个数即为 nm(mk)\frac{n}{m}\binom{m}{k}。

广义 Raney 引理：若整数序列 x1,…,xmx_1, \dots, x_m 满足 xi≤1x_i \leq 1 且 ∑i=1mxi=n\sum_{i = 1}^m x_i = n，则它的 mm 个循环移位中恰好有 nn 个满足前缀和均为正数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#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;
}