组合数

885. 求组合数 I(1<=n<=10000,1<=a,b<=2000)
题意：给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
思路：公式：C(i,j)=C(i-1,j)+C(i-1,j-1)，根据这个公式之间递推。

#include
using namespace std;
const int N=2010,MOD=1e9+7;
int a[N][N];
void init()
{
	for(int i=0;i 
886. 求组合数 II（1≤n≤10000,1≤b≤a≤105）（预处理出每个数的阶乘）
 题意：给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
 
思路：公式C(a,b)=a!/b!*(a-b)!。与处理出每个数的阶乘fact[i]，因为a/b%p!=a%p/b%p的，所以用逆元将除法用乘法来表示，用infact[i]表示1/i的阶乘。所以C(a,b)=fact[a]*infact[b]*infact[a-b]。注意：要取模的话就得全都取，不能中间有的没有取，不然会影响最终结果(1*3)%3=0,1%3*3%3=0。
 
#include
using namespace std;
typedef long long ll;
const int N=1e5+10,MOD=1e9+7;
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()
{
	int n,x,y;
	fact[0]=infact[0]=1;
	for(int i=1;i 
887. 求组合数 III（1<=n=<20,1≤b≤a≤10^18 ,1≤p≤105）
思路：卢卡斯定理lucas，C(a,b)=C(a%p,b%p)*C(a/p,b/p)(mod p)（同余）
 
#include
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=a,j=1;j<=b;i--,j++)//组合公式a*(a-1)*(a-2)*...*(a-b+1)/b!
	{
		res=(ll)res*i%p;
		res=(ll)res*qmi(j,p-2,p)%p;//i的逆元来表示倒数，这样乘法才可以边乘边模
	}
	return res;
}
int lucas(ll a,ll b,ll p)
{
	if(a 
888. 求组合数 IV（高精度求组合数）
思路：从最原始的公式入手C(a,b)=a!/b!*(a-b)!，将a!，b!,(a-b)!质因数分解，统计出每个质因子
 出现的次数，用分子的质因子的次数减去分母的sum[i]，最后用高精度乘法将sum[i]一一乘起来。
a!里质数p出现的次数为t=a/p+a/p2+..+a/pk。
 
#include
#include
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)//获得a!里p出现的次数
{
	int res=0;
	while(n)
	{
		res+=n/p;
		n/=p;
	}
	return res;
}
vector mul(vector a,int b)
{
	vector c;
	int t=0;
	for(int i=0;i>a>>b;
	get_primes(a);//筛选1-a里的质数
	for(int i=0;i res;
	res.push_back(1);
	for(int i=0;i=0;i--)
		cout< 
889. 满足条件的01序列
 
思路：把所有序列抽象成一条一条不同的路径，假设0是向右走，1是向上走，所以就是从（0，0）→（n，n)，有多少条合法的路径，因为sum(0)>=sum(1)，所以就是从(0,0)→(n,n)在指向y=x上及下面，既是不经过y=x+1这条线有多少条路径。所有的路径为C(2n,n)，不合法的路径（经过y=x+1的）C(2n,n-1)，就是从(0,0)→(n-1,n+1)的所有路径C(2n,n-1)，所以最终答案就是C(2n,n)-C(2n,n-1)，化简之后为C(2n,n)/(n+1)，这个数是一个卡特兰数。
 
 
 
 
#include
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;
	cin>>n;
	int a=2*n,b=n,res=1;
	for(int i=a,j=1;j<=b;i--,j++)
	{
		res=(ll)res*i%mod;
		res=(ll)res*qmi(j,mod-2,mod)%mod;
	}
	res=(ll)res*qmi(n+1,mod-2,mod)%mod;//res=res/(n+1);因为是除的就不能满足同余，所以要转为乘法，用逆元来表示
	cout<