EOJ

EOJ3006. 计算多项式的系数II

二项式系数与lucas定理

Posted by WeiYang on 2018-06-05

题目链接:EOJ3006

题意


给定一个多项式\({(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课中的费马小定理和欧拉定理。

代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}