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

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

    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 引理

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

    #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;
    }