算法:数学知识 + 组合计数
时间复杂度:$O(K^2)$
求解 $(ax + by)^k$ 对应 $x^ny^m$ 且 $m + n = k$ 项的系数,显然 $C^n_k$($C^m_k$) 为 $x^ny^m$ 的总的个数,在多项式中 $x$ 系数为 $a$,$y$ 系数为 $b$,则每个 $x^ny^m$ 的系数必定为 $a^nb^m$,所以答案就是 $C^n_ka^nb^m$。
其中需要注意的是取模,特别是在计算 $a^n$、$b^m$ 时,先对 $a$,$b$ 取模,再边乘边取模,以防溢出。
当然,这题还可以用快速幂优化一下。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010, MOD = 10007;
int a, b, k, n, m;
int C[N][N];
int power(int a, int b)
{
a = a % MOD;
int res = 1;
while (b--) res = res * a % MOD;
return res;
}
int main()
{
cin >> a >> b >> k >> n >> m;
for (int i = 0; i <= k; ++i) {
for (int j = 0; j <= i; ++j) {
if (!j) C[i][j] = 1;
else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
int x = power(a, n);
int y = power(b, m);
cout << C[k][n] * x % MOD * y % MOD << endl;
return 0;
}