EOJ3006. 计算多项式的系数II

题目链接: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课中的费马小定理和欧拉定理。

代码


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

   转载规则


《EOJ3006. 计算多项式的系数II》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
A Minimal Span-Based Neural Constituency Parser A Minimal Span-Based Neural Constituency Parser
论文地址:ACL17代码地址:github 今天要分享的是伯克利2017年发表在ACL的一篇成分句法分析论文,论文和代码地址都已经放在上面了,代码里还给出了处理过的PTB数据集,使用起来非常方便。 摘要 本文提出了一种不同于传统方法的成
2018-06-28
下一篇 
EOJ2854. 统计特定字串模式的个数 EOJ2854. 统计特定字串模式的个数
题目链接:EOJ2854 题意 在0和1组成的长度为$n(1 \le n \le 31)$的字符串中,统计包含$m(1 \le m \le n)$个连续1子串的字符串的个数。 题解 这题要用到的算法思想是动态规划。 首先令$f(n, m
2018-06-05
  目录