组合数取模

对于$C^{m}_{n}$%p的，根据n，m，p的数据范围来用不同的方法来求

1<=m<=n<=1000, p任意

数目比较少，而且a,b的值也比较小我们可以用递推的方法,利用性质3. C(a,b)=C(a-1,b-1)+C(a-1,b).

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
const int maxn=2e3+5;
int C[maxn][maxn];
const int mod=1e9+7;
void init()
{
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)
                C[i][j]=1;
            else
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}
int main()
{
    int t;
    cin>>t;
    init();
    int a,b;
    while(t--)
    {
        cin>>a>>b;
        cout<<C[a][b]<<endl;
    }
}

1<=m<=n<=10⁶, p 任意

数目比较少，但是a和b比较大,但是一个阶乘就超过int范围了,所以我们要用到long long还有逆元的定理,边乘边除,利用1. C(n,m)=n! / ( (n-m)! * m! )

namespace CNM {
    const int N = 2e6 + 5;
    ll mod = 1e9+7;
    ll quick(ll x, ll n)
    {
        ll res = 1;
        while (n)
        {
            if (n & 1) res = (res*x) % mod;
            x = x * x%mod;
            n >>= 1;
        }
        return res;
    }
    ll inv(ll x) { return quick(x, mod - 2); }
    ll fac[N], invfac[N];
    void init()
    {
        fac[0] = 1;
        for (int i = 1; i < N; ++i) fac[i] = (fac[i - 1] * i) % mod;
        invfac[N - 1] = inv(fac[N - 1]);
        for (int i = N - 2; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
    }
    ll C(int n, int m)
    {
        if (n < m || m < 0) return 0;
        return fac[n] * invfac[m] % mod*invfac[n - m] % mod;
    }
}

1<=m<=n<=10¹⁸, 1<=p<=10⁵

组合数比较大,还有要取余,需要利用组合数的卢卡斯定理
C(n,m)%p=C(n/p,m/p) * C(n%p,m%p)%p卢卡斯定理对较大的组合数对素数p取模

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,a,b,p;
ll ksm(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
ll C(ll a,ll b,ll p)
{
    if(b>a) return 0;
    ll x=1,y=1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        x=x*j%p;
        y=y*i%p;
    }
    return x*ksm(y,p-2,p)%p;
}
ll lucas(ll a,ll b,ll p)
{
    if(a<p&&b<p)    return C(a,b,p);
    else
        return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}