题目描述
给定一个多项式(ax+by)k,请求出多项式展开后xnym项的系数。
输入格式
共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。
输出格式
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007 取模后的结果。
数据范围
0≤n,m≤k≤1000,
n+m=k,
0≤a,b≤106
输入样例:
样例
1 1 3 1 2
算法1
(暴力枚举) $O(nlgn)$
C++ 代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 10007;
int qpow(int a,int b,int p)
{
int ans =1;
while(b)
{
if(b&1)ans = (ll) ans * a % p;
a =(ll) a *a %p;
b>>=1;
}
return ans;
}
int main()
{
int a,b,m,n,k;
cin >> a >> b >> k >> n >> m;
int res =1;
for(int i=k;i>k-n;i--)res =(ll) res * i%mod;//计算{k!/(k-n)!}%mod
for(int i=1;i<=n;i++)res =(ll) res * qpow(i,mod-2,mod)%mod;//计算{n!的逆元}
a =qpow(a,n,mod)%mod;
b = qpow(b,m,mod)%mod;
res = (ll) res * a *b %mod;
cout << res<<endl;
return 0;
}