算法知识点: 组合数，二项式定理

复杂度：

解题思路：

由二项式定理：

因此， 的系数是 。

时间复杂度分析:

计算的瓶颈在计算 上，对于分母中每个数都需要做一次快速幂，因此总时间复杂度是 。

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;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ