模板题——中国剩余定理，求组合数，卡特兰数

57 阅读 0 评论 38 点赞

我是靠谱客的博主粗心手机，最近开发中收集的这篇文章主要介绍模板题——中国剩余定理，求组合数，卡特兰数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.中国剩余定理（还没太理解推导过程(lll￢ω￢)）：拓展欧几里得算法与反复迭代

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    int n;
    cin>>n;
    bool has_answer=true;
    ll m1,a1;
    cin>>a1>>m1;
    for(int i=0;i<n-1;i++)
    {
        ll m2,a2;
        cin>>a2>>m2;
        ll k1,k2;
        ll d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d)
        {
            has_answer=false;
            break;
        }
        k1*=(m2-m1)/d;
        ll t=a2/d;
        k1=(k1%t+t)%t;
        m1=a1*k1+m1;
        a1=abs(a1/d*a2);
    }
    if(has_answer) cout<<(m1%a1+a1)%a1<<endl;
    else puts("-1");
    return 0;
}

2.求组合数1 $C_a^b$

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;
const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
        if(!j) c[i][j]=1;
        else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main()
{
    int n;
    cin>>n;
    init();
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%dn",c[a][b]);
    }
    return 0;
}

3.求组合数2：求阶乘与乘法逆元

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;
const int N=100010,mod=1e9+7;
typedef long long ll;
int fact[N],infact[N];
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}
int main()
{
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=(ll)fact[i-1]*i%mod;
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%dn",(ll)fact[a]*infact[b]%mod*infact[a-b]%mod);
    }
    return 0;
}

4.求组合数3：卢卡斯定理

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}
int C(int a,int b,int p)//定义出发求组合数
{
    if(b>a) return 0;
    int res=1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2,p)%p;
    }
    return res;
}
int lucas(ll a,ll b,int p)
{
    if(a<p&&b<p) return C(a,b,p);
    return (ll)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        ll a,b;
        int p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}

5.求组合数4（不取模）

思路：① $C_a^b$ =a!/(a-b)!b! ②对①分解质因数 ③计算高精度乘法

#include <bits/stdc++.h>

using namespace std;
const int N=5010;
int primes[N],cnt;
int sum[N];//存放质因数的次数
bool st[N];
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
int get(int n,int p)//获取n中质因子p的个数
{
    int res=0;
    while(n)
    {
        res+=n/p;
        n/=p;
    }
    return res;
}
vector<int > mul(vector<int >&A,int b)
{
    vector<int >C;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        if(i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
int main()
{
    int a,b;
    cin>>a>>b;
    get_primes(a);
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        sum[i]=get(a,p)-get(a-b,p)-get(b,p);
    }
    vector<int> res;
    res.push_back(1);
    for(int i=0;i<cnt;i++)
        for(int j=0;j<sum[i];j++)
        res=mul(res,primes[i]);
    for(int i=res.size()-1;i>=0;i--) printf("%d",res[i]);
    puts("");
    return 0;
}

6.卡特兰数

$C_2n^n$ - $C_2n^n-1$ = $C_2n^n$ /(n+1) 的应用

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=100010,mod=1e9+7;
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        a=(ll) a*a%p;
        k>>=1;
    }
    return res;
}
int main()
{
   int n;
   cin>>n;
   int a=2*n,b=n;
   //使用组合数II模板
   int res=1;
   for(int i=a;i>a-b;i--) res=(ll) res*i%mod;
   for(int i=1;i<=b;i++) res=(ll) res*qmi(i,mod-2,mod)%mod;
   res=(ll) res*qmi(n+1,mod-2,mod)%mod;
   cout<<res<<endl;
    return 0;
}