[NOIP2011 提高组] 计算系数

题目描述

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

输入格式

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

输出格式

输出共一行，包含一个整数，表示所求的系数。

这个系数可能很大，输出对 $10007$ 取模后的结果。

样例 #1

样例输入 #1

1
1 1 3 1 2

样例输出 #1

1
3

提示

【数据范围】

对于 $30\%$ 的数据，有 $ 0\le k\le 10$。

对于 $50\%$ 的数据，有 $ a=1$，$b=1$。

对于 $100\%$ 的数据，有 $0\le k\le 1000$，$0\le n,m\le k$，$n+m=k$，$0\le a,b\le 10^6$。

noip2011 提高组 day2 第 1 题。

题解

题目解析

一道比较简单的题目,但是不知道为什么我错的这么离谱.

高中都学过二项式定理:

这道题与组合数有关,可以用dp打表杨辉三角,其状态转移方程为(要注意一下$j=0$的情况):

然后直接无脑写一个pow函数,不断取模就好了.

AC代码

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
#include <iostream>
using namespace std;
const int N = 1010;
const int mod = 10007;
typedef long long ll;

ll dp[N][N];

ll pow(ll x,ll n){
	ll ans = 1;
	for(int i=1;i<=n;i++)
		ans = (ans * x) % mod;
	return ans;
}

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