【题目描述】
给定一个多项式 (ax+by)^k ,请求出多项式展开后 x^n y^m 项的系数。
【输入】
输入共一行,包含 5 个整数,分别为 a,b,k,n,m ,每两个整数之间用一个空格隔开。
【输出】
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10,007 取模后的结果。
【输入样例】
1 1 3 1 2
【输出样例】
3
【提示】
数据范围与提示
对于30% 的数据,有 k≤10;
对于50% 的数据,有 a=1,b=1;
对于100% 的数据,有 0≤n,m≤k,且 n+m=k,0≤a,b≤106 。
#include <iostream>
#define ll long long
#define mod 10007
using namespace std;
ll a[1045][1034];
ll quick_pow(ll a,ll b) {
ll ret=1;
while(b) {
if(ret&1) ret=(ret*a%mod)%mod;
a=a*a%mod;
b/=2;
}
return ret%mod;
}
int main() {
ll s,b,k,m,n;
cin>>s>>b>>k>>n>>m;
s%=mod,b%=mod;
for(int i=1; i<=k; i++) {
a[i][0]=a[i][i]=1;
for(int j=1; j<=i-1; j++) a[i][j]=(a[i-1][j-1]+a[i-1][j])%mod;
}
ll ans=a[k][m];
ll Aa=1,Ba=1;
for(int i=1; i<=n; i++) Aa=Aa*s%mod;
for(int i=1; i<=m; i++) Ba=Ba*b%mod;
ans=ans*Aa%mod*Ba%mod;
cout<<ans;
return 0;
}