欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

白兔的式子 (组合)

程序员文章站 2022-04-23 09:13:48
题目 "白兔的式子" 解析 看到题目中的递推公式,应该一下子就想到杨辉三角,二项式定理中的系数${n}\choose{i}$对应着杨辉三角中的第n+1行i+1列,然后通过手玩发现结果是$\binom{n 1}{m 1}a^{n m}b^{m 1}$,发现数据是1e5,所以用阶乘求,至于有理数取余可以 ......

题目

解析

看到题目中的递推公式,应该一下子就想到杨辉三角,二项式定理中的系数\({n}\choose{i}\)对应着杨辉三角中的第n+1行i+1列,然后通过手玩发现结果是\(\binom{n-1}{m-1}a^{n-m}b^{m-1}\),发现数据是1e5,所以用阶乘求,至于有理数取余可以看

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int n = 1e5 + 20;
const int mod = 998244353;
int t, n, m, a, b;
int jc[n];

template<class t>inline void read(t &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return;
}

void init(int n = 100010) {
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) jc[i] = (jc[i - 1] * i) % mod;
}

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod, b >>= 1;
    }
    return ans;
}

int c(int n, int m) {
    return (jc[n] * qpow((jc[n - m] * jc[m]) % mod, mod - 2)) % mod;
}

signed main() {
    init();
    read(t);
    
    while (t--) {
        read(a), read(b), read(n), read(m);
        cout << ((c(n - 1, m - 1) * qpow(a, n - m)) % mod * qpow(b, m - 1)) % mod << '\n';
    }
}