[NOIP2011-提高] 计算系数

题目描述

给定整数 $a, b, k, n, m$ （保证 $n + m = k$ ），求多项式 $(by+ax)^k$ 展开后 $x^n y^m$ 项的系数，对 $10007$ 取模。输入一行五个整数；输出一个整数。样例：1 1 3 1 2 → 3。数据范围： $0 \le k \le 1000$ ， $0 \le n, m \le k$ ， $0 \le a, b \le 10^6$ 。

思路

由二项式定理， $x^n y^m$ 的系数为 $\binom{k}{n} a^n b^m$ 。用杨辉三角递推求 $\binom{k}{n} \bmod 10007$ （ $k \le 1000$ ， $O(k^2)$ ）， $a^n, b^m$ 用快速幂取模；全程不出现除法， $a$ 或 $b$ 为 $0$ 时结果自然为 $0$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# 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-10-02 09:27
# update_at: 2026-10-02 09:27

import sys
from math import comb

MOD = 10007  # 题面要求的模数


def solve() -> None:
    a, b, k, n, m = map(int, sys.stdin.read().split())

    # (ax+by)^k 中 x^n y^m 的系数 = C(k,n) * a^n * b^m
    # k ≤ 1000，comb 直接精确计算；a^n b^m 用内置快速幂取模
    ans = comb(k, n) * pow(a, n, MOD) * pow(b, m, MOD) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * 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-10-06 14:42
 * update_at: 2026-10-06 14:42
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 10007;
const int MAXK = 1005;

// 题目输入：a, b 为底数，k 为次数，n + m = k
ll a, b, k, n, m;

ll c[MAXK][MAXK]; // c[i][j] = C(i, j) mod 10007，杨辉三角递推求出

// 快速幂：返回 (base ^ exp) mod MOD，用来算 a^n 和 b^m
ll fast_pow(ll base, ll exp) {
    ll result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

// 用杨辉三角递推出 C(i, j) 对 MOD 取模的值，避免直接算大数或做除法
void build_comb() {
    for (int i = 0; i <= k; i++) {
        c[i][0] = 1;
        c[i][i] = 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);

    cin >> a >> b >> k >> n >> m;

    build_comb();

    // 二项式定理：x^n y^m 的系数 = C(k, n) * a^n * b^m
    ll ans = c[k][n] * fast_pow(a, n) % MOD * fast_pow(b, m) % MOD;
    cout << ans << endl;

    return 0;
}

[NOIP2011-提高] 计算系数

目录

题目描述

思路

参考代码