题意

给定一个多项式${(ax + by)^k}$，计算多项式展开后${x^n}{y^m}$项的系数，结果对1000000007取模。

题解

由二项式定理可以得知，${x^n}{y^m}$项的系数就是
<!–swig4–>
然后再对1000000007取模，其中${a^n}{b^m}$取模很方便，用快速幂就行了，剩下的问题就是如何求解
<!–swig6–>
这里由于$n,k$都不是很大，所以直接采用组合数计算公式求出答案，再进行取模就行了。

拓展一下，如果$n,k$都是小于$10^9$的，那么就不能直接计算了。

这时候要用到一个大组合数取模的定理，叫做lucas定理：

定理：
对于组合数取模
<!–swig10–>
其中$p$是质数。
如果令$n=sp+q,m=tp+r. (q,r那么有
<!–swig13–>
证明:
<!–swig14–>
其中$(1 + x)^n$中$x^{tp+r}$项的系数为$C_{sp + q}^{tp + r}$，而在同余号右边$x^{tp+r}$项的系数只能为$C_s^tC_q^r$。
因为假设
<!–swig20–>
所以
<!–swig21–>
而
<!–swig22–>
所以只能是
<!–swig23–>
所以
<!–swig24–>

在代码实现中，应用lucas定理之后，将$C_n^m$替换为$C_s^t$继续调用lucas定理即可。递归终止条件是$t=0$。

最后计算$C_q^r\bmod p$时直接应用组合数定义即可：
<!–swig29–>
这里还用到了逆元：
<!–swig30–>
证明详见我的另一篇博客：具体数学-第12课中的费马小定理和欧拉定理。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAXN = 1000000 + 10;
const LL MOD = 1e9 + 7;

LL f[MAXN];

LL QuickPow(LL a, LL n, LL p) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        n >>= 1;
    }
    return res;
}

LL C(LL n, LL m, LL p) {
    LL res = f[n] * QuickPow((f[m] * f[n-m]) % p, p - 2, p) % p;
    return res;
}

void init() {
    f[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        f[i] = (f[i - 1] * i) % MOD;
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    for (int t = 0; t < T; ++t) {
        LL a, b, k, n, m;
        scanf("%lld%lld%lld%lld%lld", &a, &b, &k, &n, &m);
        LL res = (((QuickPow(a, n, MOD) * QuickPow(b, m, MOD)) % MOD) * C(k, n, MOD)) % MOD;
        printf("case #%d:\n%lld\n", t, res);
    }
    return 0;
}