1 展开式
对非负整数 n,有:
(x+y)n=k=0∑n(kn)xn−kyk.这就是二项式定理。其中 (kn) 表示从 n 个不同位置中选出 k 个,组合数的含义见 排列与组合。
例如:
(x+y)3=x3+3x2y+3xy2+y3.各项的总次数都是 n。当 n=0 时,展开式只有常数项 1,对应 (00)=1。
2 系数的来源
把 (x+y)n 写成 n 个因子的乘积。分配律展开时,每个因子恰好选一个 x 或 y,再把选出的项相乘。
要产生 xn−kyk,必须恰好在 k 个因子中选择 y,其余因子选择 x。因此,需要选择的是哪些因子取 y,共有 (kn) 种,合并同类项后的系数就是 (kn)。
例如 n=3,k=1,三种选择都产生 x2y:

因子在乘积中有不同的位置,所以选择方案不同;乘法交换律又让它们产生相同的单项式。因此要把这些贡献相加,而不是只保留一项。
3 计算系数
将两个加数换成 ax、by,得到:
(ax+by)k=j=0∑k(jk)ak−jbjxk−jyj.要求 xnym 的系数,先检查 n+m=k,再取 j=m:
系数=(mk)anbm=(nk)anbm.若 n,m 是非负整数且 n+m=k,该单项式不会出现,系数为 0。注意幂次要跟随相应变量,不能把 an 与 bm 交换。
例如 (2x−y)5 中,x3y2 的系数为:
(25)⋅23⋅(−1)2=80.负号属于 y 的系数,必须一起乘方;若要求 x4y 的系数,则为 (15)⋅24⋅(−1)=−80。
3.1 例题
题目:。
输入 a,b,k,n,m,求上述系数对 10007 取模的结果。题目保证 0≤k≤1000、0≤n,m≤k、n+m=k,且 0≤a,b≤106。
在这个范围内,用杨辉三角递推组合数:
(ji)=(j−1i−1)+(ji−1),(0i)=(ii)=1.两个分支分别表示是否选中第 i 个位置。整个递推只需要加法,可以直接对模数取模;幂次部分使用 快速幂。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;
const int mod = 10007;
int c[maxn][maxn];
ll qpow(ll a, int b) {
a = (a % mod + mod) % mod;
ll answer = 1;
while (b) {
if (b & 1) answer = answer * a % mod;
a = a * a % mod;
b >>= 1;
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a, b;
int k, n, m;
cin >> a >> b >> k >> n >> m;
if (n + m != k) {
cout << 0 << '\n';
return 0;
}
c[0][0] = 1;
for (int i = 1; i <= k; ++i) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
ll answer = 1LL * c[k][n] * qpow(a, n) % mod;
answer = answer * qpow(b, m) % mod;
cout << answer << '\n';
return 0;
}
时间为 O(k2+log(n+1)+log(m+1)),空间为 O(k2)。边界 k=0、n=0 或 m=0 都需要保留:指数为零表示该因子未被选用,对乘积贡献 1。
不要先用普通整数计算阶乘再相除,结果可能早已溢出;也不能把整数除法直接照搬到模运算中。这里使用的杨辉三角递推不需要除法。
完整题解:pcs2:计算系数。
4 常用恒等式
4.1 系数和
取 x=y=1,得到:
k=0∑n(kn)=2n.组合意义是:按选取元素个数分类,所有子集共有 2n 个。这一式对 n=0 也成立。
4.2 奇偶选择
当 n≥1 时,取 x=1,y=−1,得到:
k=0∑n(−1)k(kn)=0.把偶数项与奇数项分别移到等式两侧,再结合系数和,可知:
0≤k≤nk 为偶数∑(kn)=0≤k≤nk 为奇数∑(kn)=2n−1.因此,当原集合至少含一个元素时,偶数大小子集与奇数大小子集数量相同,空集也计入偶数大小子集。n=0 时只有一个空集,交错和为 1,不能套用上式。
4.3 范德蒙德恒等式
对非负整数 r,s,k,有:
i=0∑k(ir)(k−is)=(kr+s),约定选取数量超出范围时组合数为 0。
从两个互不相交、大小分别为 r,s 的集合中,一共选 k 个元素。左侧按从第一个集合选了 i 个分类,右侧直接从并集中选择,两者统计同一件事。
也可以比较 (1+x)r(1+x)s=(1+x)r+s 两侧 xk 的系数。展开式中的系数既能表示选择数,也能用来组织分组计数。
5 相关题解
暂无相关题解