题解：多项式系数计算（二项式定理+组合数预处理）

一、解题核心思路

根据二项式定理，$(ax+by)^k$ 的展开式为：

$$(ax+by)^k = \sum_{i=0}^k \binom{k}{i} \cdot (ax)^i \cdot (by)^{k-i} $$

其中 $x^ny^m$ 项对应 $i=n$（因 $n+m=k$），因此该项的系数为：

$$\binom{k}{n} \cdot a^n \cdot b^m$$

需计算该式对 $10007$ 取模的结果。

二、关键步骤

1. 组合数预处理： 预处理 $k \leq 1000$ 范围内的组合数 $\binom{k}{n}$，利用杨辉三角递推：

   • 初始化组合数数组 $C[k+1][k+1]$，其中 $C[i][j]$ 表示 $\binom{i}{j}$。
   • 递推公式：$C[i][0] = 1$，$C[i][i] = 1$，$C[i][j] = (C[i-1][j-1] + C[i-1][j]) \mod 10007$。

2. 快速幂计算幂次： 计算 $a^n \mod 10007$ 和 $b^m \mod 10007$，使用快速幂（时间复杂度 $O(\log n)$）。

3. 最终系数计算： 系数 = $(C[k][n] \times (a^n \mod 10007) \times (b^m \mod 10007)) \mod 10007$。

三、完整代码实现

#include <iostream>
using namespace std;

const int MOD = 10007;
const int MAX_K = 1005;
int C[MAX_K][MAX_K]; // 组合数C[k][n]

// 预处理组合数
void precompute_comb(int max_k) {
    for (int i = 0; i <= max_k; ++i) {
        C[i][0] = 1;
        C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

// 快速幂：计算x^e mod MOD
long long fast_pow(long long x, int e) {
    long long res = 1;
    x %= MOD;
    while (e > 0) {
        if (e % 2 == 1) {
            res = (res * x) % MOD;
        }
        x = (x * x) % MOD;
        e /= 2;
    }
    return res;
}

int main() {
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;

    precompute_comb(k);
    long long comb = C[k][n];
    long long a_pow = fast_pow(a, n);
    long long b_pow = fast_pow(b, m);

    long long ans = (comb * a_pow) % MOD;
    ans = (ans * b_pow) % MOD;
    cout << ans << endl;

    return 0;
}

四、代码解释

1. 组合数预处理：precompute_comb 用杨辉三角递推生成 $k \leq 1000$ 的组合数，确保模 $10007$ 后的值正确。
2. 快速幂：fast_pow 高效计算幂次的模结果，避免大数溢出。
3. 系数计算：按二项式定理公式计算三项的乘积，最终对 $10007$ 取模得到结果。

五、复杂度分析

• 时间复杂度：预处理组合数为 $O(k^2)$（$k \leq 1000$，操作数约 $1e6$），快速幂为 $O(\log n + \log m)$，总时间可忽略。
• 空间复杂度：$O(k^2)$（存储组合数数组），空间开销可控。

该方法直接利用二项式定理，结合预处理和快速幂，高效解决了多项式系数的计算问题。