多項式 $(ax + by)^k$ を展開したとき、項 $x^n y^m$ の係数を $10007$ で割った余りとして求めよ。ただし、$n + m = k$ が常に成り立つ。

解法の概要

二項定理より、$(ax + by)^k$ の展開における $x^n y^m$ 項の係数は以下の式で表される：

ここで $\binom{k}{n}$ は二項係数であり、$k \leq 1000$ であるため、動的計画法（パスカルの三角形）を用いて前もって全ての組み合わせ数を計算することが可能である。

実装ポイント

• 入力値 $a, b$ は事前に $10007$ で剰余を取る。
• 二項係数 $\binom{i}{j}$ は漸化式 $\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}$ を用いて DP テーブルに格納。
• 最終的な係数は $\binom{k}{n} \cdot a^n \cdot b^m \bmod 10007$ で計算。

コード例（C++）

#include <iostream>
using namespace std;

const int MAX_K = 1005;
const int MOD = 10007;

int comb[MAX_K][MAX_K];

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

    // パスカルの三角形で二項係数を前計算
    for (int i = 0; i <= k; ++i) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
        }
    }

    long long result = comb[k][n];
    for (int i = 0; i < n; ++i)
        result = (result * a) % MOD;
    for (int i = 0; i < m; ++i)
        result = (result * b) % MOD;

    cout << result << endl;
    return 0;
}