「一本通 6.6 例 1」计算系数

题目描述

给定整数 $a,b,k,n,m$ （ $0\le n,m\le k$ 且 $n+m=k$ ， $0\le a,b\le 10^6$ ），求多项式 $(ax+by)^k$ 展开后 $x^ny^m$ 项的系数，结果对 $10007$ 取模。

输入一行 5 个整数 $a,b,k,n,m$ ；输出一行一个整数，即所求系数模 $10007$ 的值。

样例输入 1 1 3 1 2 时， $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ ， $xy^2$ 项系数为 $3$ ，样例输出 3。

思路

由二项式定理， $(ax+by)^k$ 展开后 $x^n y^m$ 项（ $m=k-n$ ）的系数唯一为 $\binom{k}{n}\cdot a^n\cdot b^m$ 。 $k\le 1000$ ，用杨辉三角递推 $O(k^2)$ 求出 $\binom{k}{n}$ ， $a^n$ 、 $b^m$ 用快速幂，全程对 $10007$ 取模即可。

参考代码

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
25#!/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-09-30 23:55
# update_at: 2026-09-30 23:55

import sys
from math import comb

MOD = 10007  # 题面指定的模数（是质数，但 k <= 1000 时直接算精确组合数再取模即可）


def coefficient(a: int, b: int, k: int, n: int, m: int) -> int:
    """二项式定理：(ax+by)^k 展开后 x^n y^m 的系数 = C(k,n) * a^n * b^m。"""
    return comb(k, n) * pow(a, n, MOD) % MOD * pow(b, m, MOD) % MOD


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


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/**
 * 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 01:38
 * update_at: 2026-10-06 01:38
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 10007; // 题面指定的模数

ll a, b, k, n, m;

// 快速幂：求 p^e mod MOD
ll qpow(ll p, ll e) {
    ll ret = 1;
    while (e > 0) {
        if (e & 1)
            ret = ret * p % MOD;
        p = p * p % MOD;
        e >>= 1;
    }
    return ret;
}

int main() {
    cin >> a >> b >> k >> n >> m;

    // 用杨辉三角递推求 C(k, n)：c[j] 表示 C(i, j)，逐行更新
    ll c[1005] = {0};
    c[0] = 1;
    for (ll i = 1; i <= k; i++)
        for (ll j = i; j >= 1; j--)
            c[j] = (c[j] + c[j - 1]) % MOD;

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

「一本通 6.6 例 1」计算系数

目录

题目描述

思路

参考代码