形式化题目
给定非负整数 a,b,k,n,m(满足 0≤k≤1000,n+m=k,0≤a,b≤106)。
求多项式 (ax+by)k 展开后单项式 xnym 的系数对 10007 取模后的值。
题目解析
由二项式定理直接提取通项公式,杨辉三角加法递推与快速幂结合。
根据二项式定理,(ax+by)k 展开式中 xnym 项的系数为 (nk)anbm。在 k≤1000 的规模下,采用杨辉三角加法递推预处理组合数,完全避开模逆元与除法运算;底数幂次则由模意义下的快速幂在 O(logk) 内求得,三者相乘即为最终答案。
思路
1. 二项式定理展开与通项公式
对于形如 (ax+by)k 的二项式展开,根据二项式定理:
(ax+by)k=r=0∑k(rk)(ax)r(by)k−r在本题中,要求包含 xnym 的项。已知 n+m=k,对应项即为 r=n 的那一项:
T=(nk)(ax)n(by)m=((nk)anbm)xnym因此,单项式 xnym 的系数为纯代数表达式:
Coeff=(nk)anbm我们需要求出的就是 ((nk)anbm)mod10007。
2. 组合数 (nk)mod10007 的计算方式
计算组合数取模通常有两种思路:
- 阶乘与费马小定理求逆元:由于模数 10007 是一个质数,可以用逆元计算 n!m!k!mod10007。
- 杨辉三角递推:利用帕斯卡恒等式 (ji)=(j−1i−1)+(ji−1)。
数据范围给出的上界为 k≤1000。
1000×1000 的二维表格仅需 106 次加法,运行耗时不超过 2 毫秒。
相比于逆元,杨辉三角只涉及整数加法和取模,逻辑最简、常数极小,且完全不需要讨论除法或特殊边界,是本题最稳健的选择。
3. 幂次项 an 和 bm 的计算
底数 a,b≤106,首先对模数 10007 取模,将底数收缩至 [0,10006] 内。
指数 n,m≤1000。
使用二进制拆分的快速幂算法,可以在 O(logn) 和 O(logm) 时间内完成计算。
4. 结果组合
最终答案为:
Ans=(((nk)mod10007)×(anmod10007)mod10007×(bmmod10007))mod10007正确性与边界
- 退化与零次幂边界:
若 n=0,则 a0=1;若 m=0,则 b0=1。快速幂实现中初始值设为 1,满足任何数的 0 次幂为 1 的数学定义。
- 底数大于模数:
输入保证 a,b≤106,在进入快速幂前先执行
base %= MOD,防止在自乘时产生超出 32 位整型的溢出。
- 运算过程溢出防护:
三个取模后的数相乘时,两两乘积可能达到 100072≈108,采用 64 位整型
long long 承接中间计算结果,步步取模。
代码
main.cpp 首先通过杨辉三角递推预处理组合数表,再调用快速幂分别计算 an 和 bm,最后输出三者模相乘的结果。
另外,目录下提供了使用逆元与费马小定理的对照验证代码 brute.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
60
61/**
* 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),当 k=1000 时进行约 5×105 次加法取模,耗时在 2ms 以内;
- 快速幂计算:分别计算 an 与 bm,耗时 O(logn+logm)≤20 次操作;
- 总时间复杂度为 O(k2+logk),总耗时不超过 3ms,极速通过。
- 空间复杂度:
- 二维数组 c[1005][1005] 占用约 4 MB 内存,空间复杂度为 O(k2),远低于 128MB 限制。
总结
本题是初等数论与组合数学在程序设计中的典型入门题。通过直接应用二项式定理通项公式,将表面上的多项式展开问题转化为组合数与模幂的离散求值。在参数规模不大(k≤1000)时,优先采用无除法的加法杨辉三角递推,既规避了逆元可能存在的各种除法边界,又保证了极简可靠的代码实现。