计算系数（acwing，数论）

题目描述：

给定一个多项式 (ax+by)^k，请求出多项式展开后 x^n*y^m 项的系数。

输入格式：

共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。

输出格式：

输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007取模后的结果。

数据范围：

0≤n,m≤k≤1000,
n+m=k,
0≤a,b≤1e6;

输入样例：

1 1 3 1 2 

输出样例：

3

分析步骤：

  第一：理清思路：

1. 通过看题目，我们清楚是要我们求解组合数的系数。所以如果我们要求解x^n*y^m的系数，系数就应该是Ck^n * a^n * b^m。那么这个Ck^n应该怎么求呢？这么多数如果我们一个一个硬算的话我们一定很困难和很耗时间的。

2. 但是我们学过组合数的递推公式就是Cp^j = Cp-1^j-1+Cp-1^j。怎么理解这个公式呢？我们可以想：现在我从一堆苹果里面随便挑出了一个苹果，题目要求我们选择j个苹果，那么现在就分为两种情况一种是包含这个我们挑中的苹果，那么我们现在只要从p-1个总数中挑出j-1个苹果就可以了所以就是Cp-1^j-1；一种是不包含这个苹果，那么我们要从p-1个苹果中挑出j个苹果。只有这两种情况那么这两种情况加到一起就可以包括了所有的可能。那么只要递推过来就可以知道后面的情况了。

  第二：书写主函数，构建整体框架：

1. 我们把值全部都输入进去，这里有一个值得注意的地方这个点很细小，就是我们的a，b必须要先求一次模，为什么呢？因为我们的a和b最大都是1e6，如果最后和模相乘一下的话就会是1e10级别的数，那么一定会溢出。所以这里一定要模一下，不然过不去！

2. 这里进入两层for循环利用好我们的递推公式，我们判断一下如果j是0的情况，就相当于从i个苹果里面选择0个的方案数，很明显一个都不选就是一种方案所以方案数就是1。

3. 最终我们得出来的答案就是res[k][n](Ck^n)个方案。

4. 我们已经把组合数的系数值算出来了，接下来就以要计算a和b的次方就行了

int main()
{cin>>a>>b>>k>>n>>m;a %= MOD , b %= MOD;for(int i = 0 ; i <= k ; i ++){for(int j = 0 ; j <= i ; j ++){if(!j) res[i][j] = 1;else res[i][j] = (res[i-1][j-1]+res[i-1][j])%MOD;}}int ans = res[k][n];for(int i = 0 ; i < n ; i ++) ans = ans * a % MOD;for(int i = 0 ; i < m ; i ++) ans = ans *b % MOD;cout<<ans;return 0;
}

代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1100 , MOD = 10007;int a,b,k,n,m;
int res[N][N] ;int main()
{cin>>a>>b>>k>>n>>m;a %= MOD , b %= MOD;for(int i = 0 ; i <= k ; i ++){for(int j = 0 ; j <= i ; j ++){if(!j) res[i][j] = 1;else res[i][j] = (res[i-1][j-1]+res[i-1][j])%MOD;}}int ans = res[k][n];for(int i = 0 ; i < n ; i ++) ans = ans * a % MOD;for(int i = 0 ; i < m ; i ++) ans = ans *b % MOD;cout<<ans;return 0;
}