求组合数_牛客博客

一、不取模直接运算。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const int maxn=62;
ll c[maxn][maxn];
ll _c[maxn][maxn];

ll C(ll n, ll m)
{
    ll res=1;
    for(ll i=1;i<=m;i++)
    {
        res=res*(n-m+i)/i;
    }
    return res;
}

int main(void)
{

    int n=maxn-1;

    for(int i=0;i<=n;i++)
    {
        c[i][0]=c[i][i]=1;
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i/2;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][i-j]=c[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
            _c[i][j]=C(i,j);
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld,%lld ",c[i][j],_c[i][j]);
            //printf("c[%d][%d]:%lld _c[%d][%d]:%lld ",i,j,c[i][j],i,j,_c[i][j]);
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

二、取模运算：
①打表：
主要时间复杂度在O（n * n）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const int maxn=1002;
ll c[maxn][maxn];
const ll mod=1000000007;

int main(void)
{

    int n=maxn-1;

    for(int i=0;i<=n;i++)
    {
        c[i][0]=c[i][i]=1;
    }

    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i/2;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1]%mod;
            c[i][i-j]=c[i][j];
        }
    }


    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",c[i][j]);
            //printf("c[%d][%d]:%lld _c[%d][%d]:%lld ",i,j,c[i][j],i,j,_c[i][j]);
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

②定义式计算：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const int maxn=1002;
const ll mod=1000000007;
const int maxx=100010;
int prime[maxx];
bool ha[maxx]={false};
int cnt=0;

void init(void)
{
    ha[1]=true;
    for(int i=2;i<maxx;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<maxx;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    return ;
}

ll cal(ll n,ll p)
{
    ll ans=0;
    while(n)
    {
        ans+=n/p;
        n/=p;
    }
    return ans;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}


ll C(ll n,ll m)
{
    ll ans=1;
    for(int i=0;i<cnt&&prime[i]<=n;i++)
    {
        ll c=cal(n,prime[i])-cal(m,prime[i])-cal(n-m,prime[i]);
        ans=ans*mypow(prime[i],c)%mod;
    }
    return ans;
}

int main(void)
{
    init();

    for(int i=1;i<=maxn;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

③定义式变形计算：
m＜p，且p是素数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const ll mod=1000000007;

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}


ll C(ll n,ll m)
{
    ll ans=1;
    for(int i=1;i<=m;i++)
    {
        ans=ans*(n-m+i)%mod;
        ans=ans*mypow(i,mod-2)%mod;
    }
    return ans;
}

int main(void)
{

    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

m任意，p是素数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const ll mod=113;

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}


ll C(ll n,ll m)
{
    ll ans=1;
    ll nump=0;
    for(int i=1;i<=m;i++)
    {
        ll temp=n-m+i;
        while(temp%mod==0)
        {
            nump++;
            temp/=mod;
        }
        ans=ans*temp%mod;

        temp=i;
        while(temp%mod==0)
        {
            nump--;
            temp/=mod;
        }
        ans=ans*mypow(temp,mod-2)%mod;
    }
    if(nump>0) return 0;
    return ans%mod;
}

int main(void)
{

    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

m任意，p任意

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;
const ll mod=24;
const int maxn=100010;
int prime[maxn];
bool ha[maxn]={false};
ll p[200],e[200]={0};
int cnt=0,res=0;


void init(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    return ;
}

void banf(ll n)
{
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        p[++res]=prime[i];
        while(n%prime[i]==0) n/=prime[i];
    }
    if(n>1) p[++res]=n;
    return ;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }

    ll g=exgcd(b,a%b,x,y);
    ll z=x;
    x=y;
    y=z-a/b*y;
    return g;
}

ll inv(ll a,ll m)
{
    ll x,y;
    ll g=exgcd(a,m,x,y);
    return (x%m+m)%m;
}

ll C(ll n,ll m)
{
    ll ans=1;
    memset(e,0,sizeof(e));
    if(m==0) return 1;
    if(m==n) return 1;
    for(int i=1;i<=m;i++)
    {
        ll temp=n-m+i;

        for(int i=1;i<=res;i++)
        {
            while(temp%p[i]==0)
            {
                e[i]++;
                temp/=p[i];
            }
        }
        ans=ans*temp%mod;


        temp=i;
        for(int i=1;i<=res;i++)
        {
            while(temp%p[i]==0)
            {
                e[i]--;
                temp/=p[i];
            }
        }
        ans=ans*inv(temp,mod)%mod;
    }

    for(int i=1;i<=res;i++)
    {
        ans=ans*mypow(p[i],e[i])%mod;
    }
    memset(e,0,sizeof(e));
    return ans%mod;
}

int main(void)
{

    init();
    banf(mod);
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#define ll long long
using namespace std;
const ll mod=24;
const int maxn=100010;
int prime[maxn];
bool ha[maxn]={false};
int cnt=0;
map<ll,ll>mp;

void init(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    return ;
}

void quanf(ll n)
{
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        while(n%prime[i]==0)
        {
            mp[prime[i]]++;
            n/=prime[i];
        }
    }
    if(n>1) mp[n]++;
    return ;
}

void _quanf(ll n)
{
    for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        while(n%prime[i]==0)
        {
            mp[prime[i]]--;
            n/=prime[i];
        }
    }
    if(n>1) mp[n]--;
    return ;
}

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

ll C(ll n,ll m)
{
    ll ans=1;
    mp.clear();
    for(int i=1;i<=m;i++)
    {
        quanf(n-m+i);
        _quanf(i);
    }
    map<ll,ll>::iterator it;
    for(it=mp.begin();it!=mp.end();it++)
    {
        ans=ans*mypow(it->first,it->second);
    }
    return ans%mod;
}

int main(void)
{

    init();
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

④预处理阶乘和逆元：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#define ll long long
using namespace std;
const ll mod=13331;
const int maxn=10010;
ll jc[maxn],jc_inv[maxn];

ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}

void init(void)
{
    jc[0]=jc_inv[0]=1;
    for(int i=1;i<maxn;i++)
    {
        jc[i]=(jc[i-1]*i)%mod;
        jc_inv[i]=mypow(jc[i],mod-2)%mod;
    }
}

ll C(ll n,ll m)
{
   return jc[n]*jc_inv[m]%mod*jc_inv[n-m]%mod;
}

int main(void)
{

    init();
    for(int i=1;i<=20;i++)
    {
        for(int j=0;j<=i;j++)
        {
            printf("%lld ",C(i,j));
        }
        putchar('\n');
        putchar('\n');
    }

    return 0;
}

⑤卢卡斯定理：
p是素数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#define ll long long
using namespace std;
ll p;
ll mypow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

ll C(ll n,ll m)
{
    ll ans=1;
    for(int i=1;i<=m;i++)
    {
        ans=(ans*(n-m+i))%p;
        ans=(ans*mypow(i,p-2))%p;
    }
    return ans%p;
}

ll Lucas(ll n,ll m)
{
    if(m==0) return 1;
    return C(n%p,m%p)%p*Lucas(n/p,m/p)%p;
}

int main(void)
{

    int t;
    cin>>t;
    while(t--)
    {
        ll n,m;
        scanf("%lld%lld%lld",&n,&m,&p);
        printf("%lld\n",Lucas(n,m));
    }

    return 0;
}