算法

(组合数，二项式定理，逆元，费马小定理) $O(nlogn)$

由二项式定理：

$(a + b)^k = \sum _{i=0} ^k C _k ^i a^i b^{k - i}$

因此，$x^ny^m$ 的系数是 $C_k^na^nb^m$，下面分别考虑每一部分如何计算：

• $a^n$ 和 $b^m$ 可以用快速幂计算；
• $C_n^m = \frac{n \times (n - 1) \times … \times (n - m + 1}{1 \times 2 \times … \times m}$，由于 $ 10007$ 是质数，因此可以用费马小定理求出分母中每个数 $t$ 对于 $10007$ 逆元： $t^{10005}$，这里也可以用快速幂计算。这样就可以将所有除法变成乘法了。

时间复杂度分析

瓶颈在计算 $C_n^m$ 上，对于分母中每个数都需要做一次快速幂，因此总时间复杂度是 $O(nlogn)$。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int mod = 10007;

int qmi(int a, int k)
{
    a %= mod;
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

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

    cin >> a >> b >> k >> n >> m;

    int res = qmi(a, n) * qmi(b, m) % mod;
    for (int i = 1, j = k; i <= n; i ++, j -- )
    {
        res = res * j % mod;
        res = res * qmi(i, mod - 2) % mod;
    }

    cout << res << endl;

    return 0;
}