题目描述
给定一个多项式(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
输出样例:
3
质因数分解
$O(nlogn)$
根据多项式展开公式可知$x^ny^m$项的系数为C^{k - m}{k} * a^n * b^m ,a的n次方和b的m次方我们可以通过连乘取模完成,但是C^{k-m}{k}中涉及到了除法,因此我们可以对通过质因数分解将其全部转化为乘法运算即可,这里的连乘运算还能用快速幂加速。
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010;
const int mod = 10007;
int a, b, k, n, m;
int primes[N], cnt;
bool st[N];
int p[N];
// C^{k - m}_{k} * a^n * b^n
//快速幂优化
int qmi(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = (LL)ans * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return ans % mod;
}
//获取n!中质因子p出现的次数
int get(int n, int p){
int s = 0;
while(n){
s += n / p;
n /= p;
}
return s;
}
//线性筛
int get_primes(){
for(int i = 2; i < N; i++){
if(!st[i]) primes[cnt++] = i;
for(int j = 0; j < cnt && i * primes[j] < N; j++){
st[i * primes[j]] = true;
if(i % primes[j] == 0) break;
}
}
}
int main(){
scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);
get_primes();
for(int i = 0, num = k; i < k - m; i++, num--){
int t = num;
for(int j = 0; primes[j] <= t; j++){
int c = 0;
while(t % primes[j] == 0){
c++;
t /= primes[j];
}
p[primes[j]] += c;
}
}
//统计(k - m)!中每个质因子的出现次数
for(int i = 0; i < cnt; i++){
int c = get(k - m, primes[i]);
p[primes[i]] -= c;
}
LL ans = 1;
for(int i = 0; i < N; i++){
if(p[i] > 0) ans = ans * qmi(i, p[i]) % mod;
}
ans = ans * qmi(a, n) % mod;
ans = ans * qmi(b, m) % mod;
printf("%lld\n", ans);
return 0;
}