<span>组合数取模</span>

参考：http://blog.csdn.net/acdreamers/article/details/8037918

NM较小

const int N = 1e6+5;
const int mod = 1e9+7;
int f[N];
int inv(int x)
{
    int ret=1,y=mod-2;
    while(y)
    {
        if(y&1)ret=1ll*ret*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return ret;
}
int C(int n,int m)
{
    if(n<m) return 0;
    int ret=1ll*f[n]*inv(f[m])%mod;
    ret=1ll*ret*inv(f[n-m])%mod;
    return ret;
}
int lucas(int n,int m)
{
    if(m == 0) return 1;
    return 1ll*C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
void init()
{
    f[0]=1;
    for(int i=1; i<=N-5; ++i)f[i]=1ll*i*f[i-1]%mod;
}

View Code

NM较大

LL n,m,p;
LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}
LL C(LL n,LL m)
{
    if(n < m)   return 0;
    if(n == m)  return 1;
    m = min(n - m,m);
    LL ans = 1,cn = 1,cm = 1;
    for(LL i = 0; i < m; ++ i)
    {
        cn = (cn * (n - i)) % p;
        cm = (cm * (m - i)) % p;
    }
    ans = (cn * quick_mod(cm,p - 2)) % p;
    return ans;
}
LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

View Code

NM较小，P较小并且可能为合数

    #include <iostream>  
    #include <string.h>  
    #include <stdio.h>  
      
    using namespace std;  
    typedef long long LL;  
    const int N = 200005;  
      
    bool prime[N];  
    int p[N];  
    int cnt;  
      
    void isprime()  
    {  
        cnt = 0;  
        memset(prime,true,sizeof(prime));  
        for(int i=2; i<N; i++)  
        {  
            if(prime[i])  
            {  
                p[cnt++] = i;  
                for(int j=i+i; j<N; j+=i)  
                    prime[j] = false;  
            }  
        }  
    }  
      
    LL quick_mod(LL a,LL b,LL m)  
    {  
        LL ans = 1;  
        a %= m;  
        while(b)  
        {  
            if(b & 1)  
            {  
                ans = ans * a % m;  
                b--;  
            }  
            b >>= 1;  
            a = a * a % m;  
        }  
        return ans;  
    }  
      
    LL Work(LL n,LL p)  
    {  
        LL ans = 0;  
        while(n)  
        {  
            ans += n / p;  
            n /= p;  
        }  
        return ans;  
    }  
      
    LL Solve(LL n,LL m,LL P)  
    {  
        LL ans = 1;  
        for(int i=0; i<cnt && p[i]<=n; i++)  
        {  
            LL x = Work(n, p[i]);  
            LL y = Work(n - m, p[i]);  
            LL z = Work(m, p[i]);  
            x -= (y + z);  
            ans *= quick_mod(p[i],x,P);  
            ans %= P;  
        }  
        return ans;  
    }  
      
    int main()  
    {  
        int T;  
        isprime();  
        cin>>T;  
        while(T--)  
        {  
            LL n,m,P;  
            cin>>n>>m>>P;  
            n += m - 2;  
            m--;  
            cout<<Solve(n,m,P)<<endl;  
        }  
        return 0;  
    }

View Code

组合数判断奇偶性有一个优美的结论

如果，那么为奇数，否则为偶数