211.计算系数
| 211. 计算系数 - AcWing题库 |
|---|
| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：3703 |
| 总尝试数：7790 |
| 来源： 《算法竞赛进阶指南》NOIP2011提高组 |
| 算法标签 二项式定理组合计数 |
题目内容
给定一个多项式 ( a x + b y ) k (ax+by)^k (ax+by)k，请求出多项式展开后 x n y m x^ny^m xnym 项的系数。
输入格式
共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。
输出格式
输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取模后的结果。
数据范围
0≤n,m≤k≤1000,
n+m=k,
0≤a,b≤10^6
输入样例：
1 1 3 1 2
输出样例：
3
题目解析
由于是齐次多项式，所以n+m一定等于k
系数可能很大，要模上10007
a和b是在100万以内
k在1000以内
多项式展开可以用二项式定理
( a + b ) n = ∑ r = 0 n C n r a n − r b r (a + b)^{n}=\sum_{r=0}^nC_{n}^ra^{n-r}b^r (a+b)n=r=0∑nCnran−rbr
证明
(
a
x
+
b
y
)
n
=
∑
k
=
0
n
C
n
k
(
a
x
)
k
(
b
y
)
n
−
k
(ax+by)^n=\sum_{k=0}^nC_{n}^k(ax)^k(by)^{n-k}
(ax+by)n=k=0∑nCnk(ax)k(by)n−k
一共是n个ax+by相乘，每一项里面不是取x这一项就是取y这一项
x的系数如果是k的话，说明有其中的k组取的是x这一项，剩下的n-k组取的是y这一项
总共有n组，从中挑出来k组取x这一项，所以一共有
C
n
k
C_{n}^k
Cnk种取法
可以发现其中的 x n y m x^ny^m xnym这一项，对应的系数就是 C k n a n b m C_{k}^na^nb^m Cknanbm
如何求组合数，看数据范围
k只有1000
可以用递推的方式来求
杨辉三角
C a b = C a − 1 b − 1 + C a − 1 b C_{a}^b=C_{a-1}^{b-1}+C_{a-1}^b Cab=Ca−1b−1+Ca−1b
证明
从a个数中，选择b个数
可以将所有选法分成两大类
比如挑第一个元素，所有包含第一个元素的方法是一类，所有不包含第一个元素的方法是另一类
如果包含第一个元素的话，就是要从剩下的a-1个元素中选b-1个元素
如果不包含第一个元素的话，就是从剩余的a-1个元素中选b个元素
因为n和m都在1000以内
所以不需要用快速幂
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 10007;
//定义一个组合数递推数组
int C[N][N];
int main()
{
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
a %= MOD, b %= MOD; //取模，防止爆
//先递推求一下组合数，有模板885题
for (int i = 0; i <= k; i ++)
for (int j = 0; j <= i; j ++)
//如果上面的数是0，方案数是1
if (!j) C[i][j] = 1;
else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
int res = C[k][n];
//接下来乘n个a和m个b
for (int i = 0; i < n; i ++) res = res * a % MOD;
for (int i = 0; i < m; i ++) res = res * b % MOD;
cout << res << endl;
return 0;
}
