【知识点】组合数学C,A(P)的板子

seasongirl 2020-01-14

话不多说上板子

typedef long long ll;
const int inf=0x3f3f3f;
const int maxn=1e9+1;
const int mod=1e9+7;
ll a[];//数组大小注意,也要与下面初始化一致
ll Pow(ll a,ll b){
    a%=mod;
    ll ans = 1;
    while(b)
    {
        if(b&1)
            ans = (ans*a)%mod;
        a = (a*a)%mod;
        b/=2;
    }
    return ans%mod;
}
ll Quk(ll a,ll b){
    a%=mod;
    ll ans = 0;
    while(b)
    {
        if(b&1)
            ans = (ans+a)%mod;
        a = (a+a)%mod;
        b/=2;
    }
    return ans%mod;
}
ll C(ll n,ll m){
    return Quk(Quk(a[n],Pow(a[n-m],mod-2)),Pow(a[m],mod-2))%mod;
}
ll A(ll n,ll m){
    return Quk(a[n],Pow(a[n-m],mod-2))%mod;
}


int main()
{
    a[0]=a[1]=1;
    for(ll i=2;i<=1000000;i++)
        a[i]=Quk(a[i-1],i);
    //C,A使用均为前面数大


    return 0;
}

相关推荐