题目描述

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

输入格式

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

输出格式

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

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

输入输出样例

输入 #1

1 1 3 1 2

输出 #1

3

说明/提示

【数据范围】

对于 30% 的数据,有 0k100\le k\le 10

对于 50% 的数据,有 a=1,b=1。

对于 100% 的数据,有 0k10000n,mkn+m=k0a,b1060\le k\le 1000,0\le n,m\le k,n+m=k,0\le a,b\le 10^6

题目分析

首先来了解下二项式定理。

该定理给出两个数之和的整数次幂注入展开为类似项之和的恒等式:

(a+b)n=i=0nCniaibni(a+b)^n=\sum\limits_{i=0}^nC_n^ia^ib^{n-i}

这里将组合数CnkC_n^k用符号(nk)\begin{pmatrix}n\\ k \end{pmatrix} 表示。

根据此定理,可以将x+y的任意次幂展开成和的形式:

(x+y)n=(n0)xny0+(n1)xn1y1+(n2)xn2y2+++(nn)x0yn(x+y)^n=\begin{pmatrix}n\\0\end{pmatrix}x^ny^0+ \begin{pmatrix}n\\1\end{pmatrix}x^{n-1}y^1+ \begin{pmatrix}n\\2\end{pmatrix}x^{n-2}y^2+\dots++ \begin{pmatrix}n\\n\end{pmatrix}x^{0}y^n

这个公式也称为二项公式或二项恒等式。

故在此,设A=by,B=ax。

(A+B)k=i=0kCkiAiBki(A+B)^k=\sum\limits_{i=0}^kC_k^iA^iB^{k-i}

得到

CkmAmBn=CkmbmanxnymC_k^mA^mB^n = C_k^mb^ma^nx^ny^m

那么系数就是CkmbmanC_k^mb^ma^n

对于组合数,利用组合数性质Cnm=Cn1m+Cn1m1C_n^m=C_{n-1}^m+C_{n-1}^{m-1} 。可在O(n×m)O(n\times m) 时间复杂度内求出组合数。幂次方可用快速幂的方式进行求解。

实现代码

#include <iostream>
#include <cstdio>
using namespace std;
/*
C(n,i)A^i B^(n-i)

C(k,m) * b^m * a^n
*/
const int M=1e4+7;
typedef long long ll;

ll mypow(ll x,ll n){//快速幂 求x^n
	if(n==0) return 1%M;
	ll tmp=mypow(x,n/2)%M;
	if(n&1) return tmp*tmp%M*x%M;
	else return tmp*tmp%M;
}
ll c[1005][1005];//c[n][m]=C(n,m)
int main(){
	ll a,b,k,n,m;
	cin>>a>>b>>k>>n>>m;
	c[0][0]=c[1][0]=c[1][1]=1;
	for(int i=2;i<=k;i++){//预处理求组合数
		for(int j=0;j<=i;j++){
			c[i][j]=(c[i-1][j]%M+c[i-1][j-1]%M)%M;
		}
	}
	cout<<c[k][m]*mypow(a,n)*mypow(b,m)%M;//利用二项式定理求系数
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)