32 数论 组合数通解和卡特兰数

1 测试组100000，数<2000 用杨辉三角 时间复杂度N2

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//组合数1 杨辉三角C(a)b=C(a-1)b+C(a-1)(b-1)
#include<bits/stdc++.h>
using namespace std;
const int N=2010,mod=1e9+7;//时间复杂度2000*2000
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;//假如j=0，也就是c[i][0]=1
           else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;//杨辉三角公式
}
int main()
{
    init();//打表，先把数都求出来
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%dn",c[a][b]);//查表中的数，输出
    }
    return 0;
}
/*到达胜利之前无法回头*/

2 测试组10000，数<=10的5次方 用预处理 时间复杂度NlogN

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//组合数2 用预处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int fact[N],infact[N];//fact存的是数的阶层，infact存的是逆元(也就是一个数的倒数的mod数)的阶层
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;//0的阶层和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);//套用公式C(a)b = a! / (b!*(a-b)!)
    }
    return 0;
}
/*到达胜利之前无法回头*/

3 测试组20 数<=10的18次方  用卢卡斯定理

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//组合数3 用卢卡斯定理 C(a)b%p =( C(a%p)(b%p) * C(a/p)(b/p) )
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int p;
int qmi(int a,int k)//快速幂模板求逆元
{
    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 res=1;
    for(int i=1,j=a;i<=b;i++,j--)//求组合数
    {
        res=(ll)res*j%p;//乘上一个j
        res=(ll)res*qmi(i,p-2)%p;//在除上一个i,也就是乘上i的逆元
    }
    return res;//返回答案
}
int lucas(ll a,ll b)
{
    if(a<p&&b<p) return C(a,b);//假如数都小于要膜的数，则直接排列组合求出
    return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;//反之套用卢卡斯定理公式,因为C(a/p)(b/p)可能很大，所以继续套用卢卡斯公式
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld%lld%d",&a,&b,&p);
        printf("%dn",lucas(a,b));//输出卢卡斯定理求出来的结果
    }
    return 0;
}
/*到达胜利之前无法回头*/

4  直接求组合数但是求出来的结果爆long long，用高精度来存储

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//组合数4 从定义出发 C(a)b=a!/b!*(a-b)!直接算出答案，答案用高精度
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int primes[N],cnt;//用来线性筛选
int sum[N];
bool st[N];//用来线性筛选
void get_primes(int n)//线性筛选质因数模板，预处理出来1~a里面的质数
{
    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();i++)
    {
        t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main()
{
   int a,b;
   scanf("%d%d",&a,&b);
   get_primes(a);
   for(int i=0;i<cnt;i++)
   {
       int p=primes[i];//当前这个质数
       sum[i]=get(a,p)-get(b,p)-get(a-b,p);//用来求一下当前这个数保含p的个数
   }
   vector<int> res;//用来存储答案
   res.push_back(1);//初始化第一个数为1
   for(int i=0;i<cnt;i++)//枚举质数
     for(int j=0;j<sum[i];j++)//枚举一下这个质数的次数
        res=mul(res,primes[i]);//高精度乘法来求，res来存答案
   for(int i=res.size()-1;i>=0;i--) printf("%d",res[i]);//输出答案
   puts("");
    return 0;
}
/*到达胜利之前无法回头*/

5 卡特兰数 给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//卡特兰数 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 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;
   scanf("%d",&n);
   int a=2*n,b=n;
   int res=1;
   //下面两步相当于求C(2n)n%mod的结果
   for(int i=a;i>a-b;i--) res=(ll)res*i%mod;//求a*(a-1)*...*(a-b+1)的膜的结果
   for(int i=1;i<=b;i++) res=(ll)res*qmi(i,mod-2,mod)%mod;//求逆元1*2*...*b的膜的结果
   res=(ll)res*qmi(n+1,mod-2,mod)%mod;//在乘以1/n+1，也就是乘以n+1的逆元
   cout<<res<<endl;//输出答案
    return 0;
}
/*到达胜利之前无法回头*/

最后

以上就是满意枫叶为你收集整理的32 数论 组合数通解和卡特兰数的全部内容，希望文章能够帮你解决32 数论 组合数通解和卡特兰数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。