题意

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

题解

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

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

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

定理：
对于组合数取模
\[C_n^m\bmod p\]
其中$p$是质数。
如果令$n=sp+q,m=tp+r. (q,r<p)$
那么有
\[C_{sp + q}^{tp + r} \equiv C_s^tC_q^r\bmod p\]
证明:
\[\begin{array}{l}{(1 + x)^n} \equiv {(1 + x)^{sp + q}} \equiv {(1 + x)^{sp}}{(1 + x)^q}\\ \equiv {({(1 + x)^p})^s}{(1 + x)^q} \equiv {(1 + {x^p})^s}{(1 + x)^q}\\ \equiv \sum\limits_{i = 0}^s {C_s^i{x^{ip}}} \sum\limits_{j = 0}^q {C_q^j{x^j}} \bmod p\end{array}\]
其中$(1 + x)^n$中$x^{tp+r}$项的系数为$C_{sp + q}^{tp + r}$，而在同余号右边$x^{tp+r}$项的系数只能为$C_s^tC_q^r$。
因为假设
\[tp + r = ip + j\]
所以
\[(t - i)p = j - r\]
而
\[ - p < - r \le j - r \le q - r < p - r \le p\]
所以只能是
\[t - i = 0,j - r = 0\]
所以
\[C_{sp + q}^{tp + r} \equiv C_s^tC_q^r\bmod p\]

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

最后计算$C_q^r\bmod p$时直接应用组合数定义即可：
\[C_q^r \equiv \frac{ {q!}}{ {r!(q - r)!}} \equiv q!{(r!(q - r)!)^{p - 2}} \equiv q!{(r!(q - r)!\bmod p)^{p - 2}}\bmod p\]
这里还用到了逆元：
\[{a^{ - 1}} \equiv {a^{p - 2}}\bmod p\]
证明详见我的另一篇博客：具体数学-第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;
}