P1313 计算系数

陈雪森 · 2019-08-21 19:31:28 · 个人记录

题意简单明了;根据二项式定理可得（ax+by）的k次答案与x的n次和y的m次有关; 本题答案即为C k n，乘a的n次b的m次;

某个数的几次方用快速幂计算即可;

本题难点在计算组合数;

组合数的计算有很多方法，在此先介绍一种。 用杨辉三角形计算组合数，可以处理较小范围的组合数，对付本题足够。 其他计算方法会在组合数博客中给出;

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a,b,k,n,m,c[1010][1010];//c数组用来存组合数； 
const int mod=10007;
#define ll long long
ll ksm(ll c,ll d){//用来求数的几次方； 
    ll ans=1;
    for(;d;d>>=1){
        if(d&1) ans=(ans*c)%mod;
        c=(c*c)%mod;
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a=ksm(a,n);
    b=ksm(b,m);
    for(int i=1;i<=k;i++){//预处理组合数； 
        c[i][0]=1;
        c[i][i]=1;
    }
    int len=min(n,m);
    for(int i=2;i<=k;i++)//用杨辉三角形求组合数； 
        for(int j=1;j<=len;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    int ans=(a*b)%mod;
    ans=(ans*c[k][len])%mod;
    cout<<ans;
    return 0;
}