题目
解析
看到题目中的递推公式,应该一下子就想到杨辉三角,二项式定理中的系数({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'; } }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603264.html