题目
题目链接
题目大意：给定多项式 $(by + ax) ^ k$，求出展开后 $x^n \times y^m$ 项的系数。$0 \le k \le 1000, 0 \le n, m \le k, n + m = k, 0 \le a, b \le 10^6$。答案为 $10007$ 取模。
思路
先考虑 $a = b = 1$ 的情况，直接用二项式定理即可。
由于 $k$ 的范围十分小，可以递推求组合数。
如果 $a, b$ 不为 $1$，将 $by, ax$ 分别看作一个整体，不难看出系数为 $\displaystyle \binom{k}{n} a^n b^m$，再套个快速幂板子就行了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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 << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}
typedef unsigned long long uLL;
typedef long long LL;
const LL mod = 10007;
LL c[1010][1010];
LL k, n, m, a, b;
LL qPow(LL x, LL y) {
LL s = 1;
while (y) {
if (y & 1LL) {
s *= x;
s %= mod;
}
y >>= 1LL;
x *= x;
x %= mod;
}
return s;
}
int main() {
read(a), read(b), read(k), read(n), read(m);
c[0][0] = 1;
for (int i = 1; i <= k; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
c[i][j] %= mod;
}
}
printf("%lld\n", ((((c[k][n] % mod) * (qPow(a, n) % mod)) % mod) * (qPow(b, m) % mod)) % mod);
return 0;
}
|