[NOIP 2011 提高组] 计算系数

GitHub跳转原题关系图返回列表

二项式定理通项系数化 + 杨辉三角模组合数预处理 + 模幂快速幂相乘

OJ: luogu

题目 ID: P1313

难度:普及

标签:数学二项式定理组合数学快速幂

创建: 2026-11-11 00:25

更新: 2026-11-10 21:30

RBook 文章:
排列与组合
快速幂

形式化题目

给定非负整数 a,b,k,n,ma, b, k, n, m(满足 0≤k≤10000 \le k \le 1000,n+m=kn + m = k,0≤a,b≤1060 \le a, b \le 10^6)。

求多项式 (ax+by)k(ax + by)^k 展开后单项式 xnymx^n y^m 的系数对 1000710007 取模后的值。

题目解析

由二项式定理直接提取通项公式,杨辉三角加法递推与快速幂结合。

根据二项式定理,(ax+by)k(ax + by)^k 展开式中 xnymx^n y^m 项的系数为 (kn)anbm\binom{k}{n} a^n b^m。在 k≤1000k \le 1000 的规模下,采用杨辉三角加法递推预处理组合数,完全避开模逆元与除法运算;底数幂次则由模意义下的快速幂在 O(log⁡k)O(\log k) 内求得,三者相乘即为最终答案。

思路

1. 二项式定理展开与通项公式

对于形如 (ax+by)k(ax + by)^k 的二项式展开,根据二项式定理:

(ax+by)k=∑r=0k(kr)(ax)r(by)k−r(ax + by)^k = \sum_{r=0}^k \binom{k}{r} (ax)^r (by)^{k-r}

在本题中,要求包含 xnymx^n y^m 的项。已知 n+m=kn + m = k,对应项即为 r=nr = n 的那一项:

T=(kn)(ax)n(by)m=((kn)anbm)xnymT = \binom{k}{n} (ax)^n (by)^m = \left( \binom{k}{n} a^n b^m \right) x^n y^m

因此,单项式 xnymx^n y^m 的系数为纯代数表达式:

Coeff=(kn)anbm\text{Coeff} = \binom{k}{n} a^n b^m

我们需要求出的就是 ((kn)anbm) mod 10007(\binom{k}{n} a^n b^m) \bmod 10007。

2. 组合数 (kn) mod 10007\binom{k}{n} \bmod 10007 的计算方式

计算组合数取模通常有两种思路:

  1. 阶乘与费马小定理求逆元:由于模数 1000710007 是一个质数,可以用逆元计算 k!n!m! mod 10007\frac{k!}{n! m!} \bmod 10007。
  2. 杨辉三角递推:利用帕斯卡恒等式 (ij)=(i−1j−1)+(i−1j)\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}。

数据范围给出的上界为 k≤1000k \le 1000。 1000×10001000 \times 1000 的二维表格仅需 10610^6 次加法,运行耗时不超过 2 毫秒。 相比于逆元,杨辉三角只涉及整数加法和取模,逻辑最简、常数极小,且完全不需要讨论除法或特殊边界,是本题最稳健的选择。

3. 幂次项 ana^n 和 bmb^m 的计算

底数 a,b≤106a, b \le 10^6,首先对模数 1000710007 取模,将底数收缩至 [0,10006][0, 10006] 内。 指数 n,m≤1000n, m \le 1000。 使用二进制拆分的快速幂算法,可以在 O(log⁡n)O(\log n) 和 O(log⁡m)O(\log m) 时间内完成计算。

4. 结果组合

最终答案为:

Ans=(((kn) mod 10007)×(an mod 10007) mod 10007×(bm mod 10007)) mod 10007\text{Ans} = \left( \left( \binom{k}{n} \bmod 10007 \right) \times (a^n \bmod 10007) \bmod 10007 \times (b^m \bmod 10007) \right) \bmod 10007

正确性与边界

  • 退化与零次幂边界: 若 n=0n = 0,则 a0=1a^0 = 1;若 m=0m = 0,则 b0=1b^0 = 1。快速幂实现中初始值设为 1,满足任何数的 0 次幂为 1 的数学定义。
  • 底数大于模数: 输入保证 a,b≤106a, b \le 10^6,在进入快速幂前先执行 base %= MOD,防止在自乘时产生超出 32 位整型的溢出。
  • 运算过程溢出防护: 三个取模后的数相乘时,两两乘积可能达到 100072≈10810007^2 \approx 10^8,采用 64 位整型 long long 承接中间计算结果,步步取模。

代码

main.cpp 首先通过杨辉三角递推预处理组合数表,再调用快速幂分别计算 ana^n 和 bmb^m,最后输出三者模相乘的结果。

另外,目录下提供了使用逆元与费马小定理的对照验证代码 brute.cpp,用于对拍验证。

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-11 00:27
 * update_at: 2026-11-11 00:27
 */
#include <iostream>

using namespace std;

using ll = long long;
const int MOD = 10007;

// 杨辉三角组合数表
int c[1005][1005];

// 快速幂计算 base^exp % MOD
ll quick_pow(ll base, ll exp) {
    ll ans = 1 % MOD;
    base %= MOD;

    while (exp > 0) {
        if (exp & 1) ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }

    return ans;
}

// 预处理组合数 C(i, j)
void init_comb(int limit) {
    for (int i = 0; i <= limit; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    int k, n, m;
    if (!(cin >> a >> b >> k >> n >> m)) return 0;

    init_comb(k);

    ll comb_kn = c[k][n];
    ll a_pow_n = quick_pow(a, n);
    ll b_pow_m = quick_pow(b, m);

    ll ans = comb_kn * a_pow_n % MOD * b_pow_m % MOD;

    cout << ans << "\n";

    return 0;
}

复杂度

  • 时间复杂度:
    • 杨辉三角预处理:O(k2)O(k^2),当 k=1000k = 1000 时进行约 5×1055 \times 10^5 次加法取模,耗时在 2ms 以内;
    • 快速幂计算:分别计算 ana^n 与 bmb^m,耗时 O(log⁡n+log⁡m)≤20O(\log n + \log m) \le 20 次操作;
    • 总时间复杂度为 O(k2+log⁡k)O(k^2 + \log k),总耗时不超过 3ms,极速通过。
  • 空间复杂度:
    • 二维数组 c[1005][1005]c[1005][1005] 占用约 4 MB 内存,空间复杂度为 O(k2)O(k^2),远低于 128MB 限制。

总结

本题是初等数论与组合数学在程序设计中的典型入门题。通过直接应用二项式定理通项公式,将表面上的多项式展开问题转化为组合数与模幂的离散求值。在参数规模不大(k≤1000k \le 1000)时,优先采用无除法的加法杨辉三角递推,既规避了逆元可能存在的各种除法边界,又保证了极简可靠的代码实现。