题解 P1313 【计算系数】

aiyougege · 2018-03-27 13:54:47 · 题解

计算系数

Solution

　　根据二项式定理,

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

那么

(ax+by)^k=\sum_{p=0}^kC_{k}^p(ax)^p(by)^{k-p}=\sum_{p=0}^k(C_{k}^pa^pb^{k-p})x^py^{k-p}

算a^n,b^m需要用快速幂.

可以根据组合式的递推公式算组合数.我是这么写的. C_n^m=C_{n-1}^m+C_{n-1}^{m-1}
或者是利用组合数的定义式,但是因为有取余, 所以要用逆元. C_n^m=\frac{n!\mod 10007}{m!(n-m)!\mod 10007}=n!\times [m!(n-m)!]^{-1}\mod 10007
其中[m!(n-m)!]^{-1}为逆元, 这个可以直接用费马小定理, 正好前面写了快速幂, 岂不是美滋滋.

Code

#include<cstdio>
#define N 1005
#define mod 10007
using namespace std;

#define int long long
int c[N][N];
int a,b,k,n,m;
int pow(int x,int y){
    int ans=1,pas=x;
    while(y){
        if(y&1)ans*=pas%mod,ans%=mod;
        pas=(pas*pas)%mod;
        y>>=1;
    }
    return ans%mod;
}

int dfs(int n,int m){
    if(!m)return c[n][m]=true;if(m==1)return c[n][m]=n;
    if(c[n][m])return c[n][m];
    if(n-m<m)m=n-m;
    return c[n][m]=(dfs(n-1,m)+dfs(n-1,m-1))%mod;
}

main(){
    //freopen("factor.in","r",stdin);
    //freopen("factor.out","w",stdout);
    scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);
    c[1][0]=c[1][1]=1;a%=mod;b%=mod;
    int ans=1;
    ans*=(pow(a,n)*pow(b,m))%mod;
    if(n>m)n=m;
    ans*=dfs(k,n)%mod;ans%=mod;
    /*for(int i=1;i<=k;++i){
        for(int j=0;j<=i;++j)
            printf("%d ",c[i][j]);
        printf("\n");
    }*/
    printf("%lld",ans);
    return 0;
}