題目
給定一個多項式$ (ax + by)^k$ ,請求出多項式展開後 $xnym $項的系數。
分析
根據二項式定理,有 ( a x + b y ) k = ∑ i = 0 k C k i a i b k − i x i y k − i (ax+by)^k=\sum_{i=0}^kC_k^ia^ib^{k-i}x^iy^{k-i} (ax+by)k=i=0∑kCkiaibk−ixiyk−i,是以 x n y m x^ny^m xnym項的系數為 C k a n b m C_ka^nb^m Ckanbm,然後通過快速幂和乘法逆元求出答案。
代碼
#include <cstdio>
#define mod 10007
using namespace std;
typedef long long ll;
ll a,b,k,n,m,ans;
ll ksm(ll x,ll y){
ll ans=1;
while (y){
if (y&1) ans=ans*x%mod;
x=x*x%mod; y>>=1;
}
return ans;
}
ll c(ll n,ll m){
ll ans=1;
for (ll i=n-m+1;i<=n;i++) ans=ans*i%mod;
for (ll i=1;i<=m;i++) ans=ans*ksm(i,mod-2)%mod;
return ans;
}
int main(){
scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);
ans=ksm(a,n)*ksm(b,m)%mod*c(k,n)%mod;
return !printf("%lld",ans);
}