1648：【例 1】「NOIP2011」计算系数

题目描述

给定一个多项式 $(ax + by)^k$，请求出多项式展开后 $x^n y^m$ 项的系数。

输入格式

输入共一行，包含 $5$ 个整数，分别为 $a, b, k, n, m$，每两个整数之间用一个空格隔开。

输出格式

输出共 $1$ 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 $10007$ 取模后的结果。

样例

样例输入 #1

1 1 3 1 2

样例输出 #1

3

样例解释 #1

• $(ax + by)^k = (x + y)^3$（因为 $a=1, b=1$）。
• 展开后 $x^1 y^2$ 的系数：$(x+y)^3 = x^3 + 3x^2 y + 3x y^2 + y^3$，所以 $x y^2$ 的系数为 $3$。
• 输出 $3$。

数据范围

• 对于 $30\%$ 的数据，有 $k \le 10$；
• 对于 $50\%$ 的数据，有 $a = 1, b = 1$；
• 对于 $100\%$ 的数据，有 $0 \le n, m \le k$，且 $n + m = k$，$0 \le a, b \le 10^6$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：根据二项式定理：

$$(ax + by)^k = \sum_{i=0}^{k} \binom{k}{i} (ax)^i (by)^{k-i} = \sum_{i=0}^{k} \binom{k}{i} a^i b^{k-i} x^i y^{k-i}$$

因此，$x^n y^m$ 项对应 $i = n$，且 $k - i = m$，所以 $n + m = k$（题目已保证）。该项的系数为：

$$\binom{k}{n} a^n b^m$$

所以需要计算 $\binom{k}{n} \times a^n \times b^m \bmod 10007$。

由于 $k$ 可能很大（$k = n+m$，$n,m$ 可达 $k$，但 $k$ 未给出上限，不过从数据范围看 $k$ 不会特别大？实际上题目未给出 $k$ 的上限，但 $n,m \le k$ 且 $n+m=k$，所以 $k$ 可能达到 $10^3$ 或更高？但 $a,b \le 10^6$，$k$ 可能也较大。但根据组合数计算，我们需要 $\binom{k}{n}$ 模 $10007$，可以用组合数公式 $\binom{k}{n} = \frac{k!}{n! (k-n)!}$，但 $k$ 可能很大，不能直接计算阶乘。

由于模数 $10007$ 是质数（检查：$10007$ 是质数），我们可以使用费马小定理求逆元，配合预处理阶乘和逆元来计算组合数。但 $k$ 可能大于 $10007$，此时需要用到 Lucas 定理 计算组合数模质数。

Lucas 定理：对于质数 $p$，有

$$\binom{n}{m} \bmod p = \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \bmod p}{m \bmod p} \bmod p$$

这样可以处理 $n, m$ 较大的情况。

因此，算法步骤：

1. 读入 $a, b, k, n, m$。
2. 计算 $C = \binom{k}{n} \bmod 10007$（使用 Lucas 定理）。
3. 计算 $a^n \bmod 10007$ 和 $b^m \bmod 10007$（快速幂）。
4. 答案 $ans = C \times a^n \times b^m \bmod 10007$。

注意：$a, b$ 可能大于 $10007$，先取模。$n, m$ 可能大于 $10007$，但指数可以对 $\varphi(10007)=10006$ 取模？因为 $10007$ 是质数，根据费马小定理，$a^{p-1} \equiv 1 \pmod{p}$，所以 $a^n \bmod p = a^{n \bmod (p-1)} \bmod p$（前提是 $a$ 不是 $p$ 的倍数）。但 $a$ 可能为 $0$，需要特判：如果 $a \equiv 0 \pmod{10007}$ 且 $n > 0$，则 $a^n \equiv 0$；如果 $n=0$，则 $a^0 = 1$。同样处理 $b$。

因此，计算 $a^n \bmod 10007$ 时，先让 $a \bmod= 10007$，如果 $a=0$ 且 $n>0$，结果为 $0$；否则用快速幂计算 $a^{n \bmod 10006} \bmod 10007$（因为 $10006 = 10007-1$）。但注意：当 $a$ 与 $10007$ 互质时，费马小定理才成立；如果 $a$ 是 $10007$ 的倍数，则 $a \equiv 0 \pmod{10007}$，直接得 $0$（除非 $n=0$）。所以可以统一处理：先取模 $a$，如果 $a=0$ 且 $n>0$，则 $a^n=0$；否则用快速幂计算 $a^n \bmod 10007$（指数 $n$ 不需要模 $10006$，因为 $n$ 可能很大，但快速幂可以处理大指数，取模即可）。

实际上，因为 $10007$ 是质数，快速幂计算 $a^n \bmod 10007$ 时，指数 $n$ 不需要模 $10006$，因为快速幂每次乘取模，复杂度 $O(\log n)$，$n$ 可能很大（$k$ 可能很大），但 $\log n$ 可以接受。但 $k$ 可能达到 $10^9$？题目未给出上限，但 $n,m \le k$，且 $a,b \le 10^6$，但 $k$ 可能也很大。不过快速幂 $O(\log n)$ 可以处理 $10^9$ 的指数。

但 Lucas 定理需要计算 $\binom{k}{n} \bmod 10007$，其中 $k$ 可能很大，但 Lucas 定理将 $k$ 和 $n$ 表示为 $p$ 进制数，递归计算，复杂度 $O(\log_p k)$。

实现 Lucas 定理需要预处理 $0$ 到 $p-1$ 的阶乘和阶乘逆元。$p=10007$，可以预处理 $fac[i] = i! \bmod p$，$inv[i] = (i!)^{-1} \bmod p$，则 $\binom{n}{m} \bmod p = fac[n] \cdot inv[m] \cdot inv[n-m] \bmod p$（当 $0 \le m \le n \le p-1$）。

对于 $k > p$ 的情况，用 Lucas 定理递归。

注意：$n, m$ 满足 $n+m=k$，所以 $k-n=m$。

因此，完整算法：

1. 预处理 $fac[0..10006]$ 和 $inv[0..10006]$。
2. 读入 $a, b, k, n, m$。
3. 计算 $C = lucas(k, n)$。
4. 计算 $A = pow_mod(a \% MOD, n, MOD)$。
5. 计算 $B = pow_mod(b \% MOD, m, MOD)$。
6. 输出 $C \times A \% MOD \times B \% MOD$。

其中 $MOD = 10007$。

注意：$a$ 或 $b$ 可能为 $0$，且 $n$ 或 $m$ 为 $0$ 时，$0^0$ 在数学上未定义，但在本题中，当指数为 $0$ 时，该项视为 $1$（因为 $x^0 = 1$）。所以需要特判：如果 $n=0$，则 $a^n = 1$；如果 $n>0$ 且 $a \% MOD == 0$，则 $a^n \% MOD = 0$。类似处理 $b$。

另外，组合数 $\binom{k}{n}$ 在 $n<0$ 或 $n>k$ 时为 $0$，但题目保证 $0 \le n,m \le k$ 且 $n+m=k$，所以 $n$ 在 $[0,k]$ 内。