c/c++语言开发共享白兔的式子 (组合)

题目

解析

看到题目中的递推公式，应该一下子就想到杨辉三角，二项式定理中的系数({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';     } }