-
难度:
Easy
。
考察二项式定理的基本应用。
正解
发现存在式子 \((ax+by)^k\),容易想到二项式定理。
二项式定理:
\[(x+y)^n=\sum\limits_{i=0}^{n}{n\choose i}x^iy^{n-i} \]
令 \(p=ax,q=by\),那么原式变为 \((p+q)^k\)。
那么此时 \(p^n\times q^m\) 的系数为 \({k\choose n}\)。
这一项即为:
\[{k\choose n}p^nq^m=\left({k\choose n}a^nb^m\right)x^ny^m \]综上,系数就是 \({k\choose n}a^nb^m\)。
\({k\choose n}\) 有很多种方法求解,这里使用公式法。
代码
#include <bits/stdc++.h>
#define int long long
const int MOD = 10007;
const int N = 1e3 + 10;
int a, b, k, n, m, fact[N], inv_fact[N];
int qpow(int a, int b) {
int ans = 1;
a %= MOD;
for (; b; b >>= 1) {
if (b & 1) (ans *= a) %= MOD;
(a *= a) %= MOD;
}
return ans;
}
void init() { // 预处理
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= k; ++i) {
fact[i] = fact[i - 1] * i % MOD;
inv_fact[i] = inv_fact[i - 1] * qpow(i, MOD - 2) % MOD;
}
}
int C(int n, int m) {
if (m > n) return 0;
if (m == n) return 1;
return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}
signed main() {
std::cin >> a >> b >> k >> n >> m, init();
std::cout << C(k, n) * qpow(a, n) % MOD * qpow(b, m) % MOD << std::endl;
return 0;
}
标签:return,LGP1313,int,题解,inv,choose,fact,MOD
From: https://www.cnblogs.com/oier-wst/p/18434388/luogu-P1313-solution