求组合数
一、组数多，a,b范围较小——O(n^2)
1、思路
正常的求解公式是
我们通过公式
这一步的要计算的数，可以通过上一步计算的结果得来，逐层迭代，把每一层都处理出来，这样多次询问就省时间
2、代码模板：
#include<iostream>
using namespace std;
const int N=2010;
const int mod=1e9+7;
int c[N][N];
int n;
void init()
{
for(int i=0;i<N;i++)//从0到N枚举a
for(int j=0;j<=i;j++)//从0到i枚举b
{
if(!j)//当j为0时
c[i][j]=1;
else
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;//公式
}
}
int main()
{
scanf("%d",&n);
init();
while(n--)
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",c[a][b]);
}
return 0;
}
二、组数少，a,b范围大——O(logn)
1、思路
我们直接通过公式计算每一组的数据
逆元就是在mod意义下，不能直接除以一个数，而要乘以它的逆元。
图来自acw_weian，
对于每一个数我们都通过快速幂的方式来计算
求逆元是因为(a/b)%p不能分开运算。
2、代码模板：
#include<iostream>
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
typedef long long ll;
int fact[N],infact[N];//fact正常，infact为逆元
int qmi(int a,int k,int p)//求逆元，即求a^k
{
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("%lld\n",(ll)fact[a]*infact[b]%mod*infact[a-b]%mod);//公式法
}
return 0;
}
三、组数非常小，但a,b范围巨大10^18——O(p*logp*logpN)
1、思路
由卢卡斯定理可以得到一个公式：
具体不再证明（没听懂）
2、代码模板：
#include<iostream>
using namespace std;
typedef long long ll;
int p;
int qmi(int a,int k)//求逆元,即a^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(ll a,ll b)//求组合
{
int res=1;
for(int i=1,j=a;i<=b;i++,j--)
{
res=(ll)res*j%p;//j从a到a-b+1，乘的分子
res=(ll)res*qmi(i,p-2)%p;//i从1~b，乘的逆元，分母
}
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;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
ll a,b;//ll
scanf("%lld %lld %d",&a,&b,&p);
printf("%d\n",lucas(a,b));
}
return 0;
}
四、用高精度算出一组a,b
1、思路
对于只有一组数据，我们按照原公式算，但思路不同
如果我们先对分子算高精度乘法，再对分母算高精度乘法，最后分子分母算高精度除法，非常耗时间
我们可以改变一下思路，能不能少乘一些？既然是分数，是不是可以先约分一下？
又想到之前学的任何一个数n都可以分解成几个质数的积，我们可以想到，先上下分别枚举质因子，并且分别算出上下每个质因子的个数
将个数相减，就能少乘不少数，而且还不用写高精度除法。
对于a!求其中质因子p的个数，为
这一步的时间复杂度为O（logn）
2、代码模板：
#include<iostream>
#include<vector>
using namespace std;
const int N=5e3+10;
int primes[N],cnt=0;
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;//相当于求原来的n/p*p运行一次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+=b*a[i];
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++)
sum[i]=get(a,primes[i])-get(b,primes[i])-get(a-b,primes[i]);//记录第i个质因子的个数
vector<int> res;
res.push_back(1);//乘法，刚开始要为1，不然乘出来全是0
for(int i=0;i<cnt;i++)//遍历质因子
for(int j=0;j<sum[i];j++)//每个质因子sum[i]个
res=mul(res,primes[i]);
for(int i=res.size()-1;i>=0;i--)//逆序输出，因为在vector中我们是逆序计算和储存的
printf("%d",res[i]);
return 0;
}
五、卡特兰数
1、思路
思路非常巧妙的一类问题，这道题，对于n个1和n个0，组成长为2n的序列，保证每前i个数内都有0 的个数都不少于 1 的个数
我们可以用图像表示
约定：0是向右走一格
1是向上走一格
我们以6个0，6个1共12个点为例
从(0,0)到(6,6)的每一条路径就是一种方案数
如果要保证cnt[0]>=cnt[1]，即有x>=y。
所以不难得到绿线。即正确的路径需要保证不超过绿线，只能在绿线下面，右下方。
对于红线，只要路径与红线有交点，就不符合题意。
所以对于答案的个数res，用总方案数-过红线的方案数就是答案
从(0,0)到(6,6)的总方案数为
对于任意一个过红线的的路径，如图中的橙线
找到橙线与红线第一次相交的点，将相交点后的橙线路径关于红线轴对称，一定会到达（5，7）
所以过红线的方案数为
由此我们可以推出来一般公式：
2、代码模板:
#include<iostream>
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;
for(int i=a;i>a-b;i--)//计算从2n~n的阶乘
res=(ll)res*i%mod;
for(int i=1;i<=b;i++)//计算从1~n逆元的阶乘
res=(ll)res*qmi(i,mod-2,mod)%mod;
res=(ll)res*qmi(n+1,mod-2,mod)%mod;//最后再乘上n+1的逆元
printf("%d",res);
return 0;
}
游卡开奖36人在聊