题目描述

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

前置知识

二项式定理、快速幂、求组合数

二项式定理:

$$(a+b)^n=\sum_{k=0}^n C_{n}^{k} a^kb^{n-k}$$

$C_a^b$ 为组合数

问题转换

$$(ax+by)^k=\sum_{n=0}^k C_k^n (ax)^n (by)^{k-n}$$

所以 $x^ny^m$的系数为 $$C_k^n a^nb^{k-n}$$

code

// Problem: P1313 [NOIP2011 提高组] 计算系数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1313
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: tw_luo

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int mod=10007;
const int N=1010;

int a,b,k,n,m;
int fac[N],ifac[N];

int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return res;
}

void init(){
    fac[0]=1,ifac[0]=1;
    for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<N;++i) ifac[i]=qpow(fac[i],mod-2);
}

int C(int a,int b){
    if(b>a) return 0;
    return 1LL*fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}

int main(){
    init();
    cin>>a>>b>>k>>n>>m;
    cout<<1LL*C(k,n)*qpow(a,n)%mod*qpow(b,m)%mod<<"\n";

    return 0;   
}