求解组合数的方法
递推法C(a,b)=C(a-1,b)+C(a-1,b-1) O(n^2)
注意f[0][0]=1,0<=a,b<=1e4
#include<iostream>
using namespace std;
const int N=2010,mod=1e9+7;
int f[N][N];
int main()
{
int n;
cin>>n;
for(int i=0;i<=2000;i++)
{
for(int j=0;j<=i;j++)
{
if(!j) f[i][j]=1;
else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
while(n--)
{
int a,b;
cin>>a>>b;
cout<<f[a][b]<<endl;
}
}
逆元 O(nlogn)
注意初始化fact[0]=infact[0]=1,0<=a,b<=1e5
C(a,b)%mod=[a!/(b!*(a-b)!)]%mod=（a!*b!的逆元*(a-b)!的逆元）%mod
a的逆元理解成模意义下的1/a
求a的逆元在模数是质数的情况下就是a的mod-2次方,否则需要换其他的方法求逆元(欧拉函数、拓展欧几里得)
也可以当模数不是质数的时候采用高精度的方法中的思想,利用质因数分解来求C
#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010,mod=1e9+7;
LL fact[N],infact[N];
LL qmi(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1) res=(res*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return res;
}
int main()
{
int n;
cin>>n;
fact[0]=infact[0]=1;
for(int i=1;i<=100000;i++)
{
fact[i]=i*fact[i-1]%mod;
infact[i]=qmi(fact[i],mod-2)%mod;
}
while(n--)
{
LL a,b;
cin>>a>>b;
cout<<fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
}
}
高精度(题目没有要求求余数情况下)O(nloglogn)
利用的是质因数分解的思想
C(a,b)%mod=[a!/(b!*(a-b)!)]
那么只需要将分子和分母的质因数次数进行相减,最后得到的质因子的次数,再将质因数相乘即可
问题就变成了如何求阶乘的各个质因子次数——>AcWing197.阶乘分解
#include<iostream>
#include<vector>
using namespace std;
const int N=5010;
int primes[N],st[N],cnt;
int c[N];
void init()
{
for(int i=2;i<N;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<N;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
vector<int> multi(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;
cin>>a>>b;
init();
//C(a,b)=a!/b!(a-b)!
for(int i=0;i<cnt;i++)
{
int p=primes[i];
for(int j=a;j;j/=p) c[p]+=j/p;
for(int j=b;j;j/=p) c[p]-=j/p;
for(int j=a-b;j;j/=p)c[p]-=j/p;
}
vector<int> res;
res.push_back(1);
for(int i=0;i<cnt;i++)
{
int t=primes[i];
for(int j=0;j<c[t];j++)
res=multi(res,primes[i]);
}
for(int i=res.size()-1;i>=0;i--) cout<<res[i];
}
封装成函数
int get_cnt(int n,int p) //n的阶乘在质因子p下的次数
{
int s=0;
while(n)
{
s+=n/p;
n/=p;
}
return s;
}
int C(int a,int b,int p) //C(a,b)%p a!/(b!*(a-b)!)
{
int res=1;
for(int i=0;i<cnt;i++)
{
int t=primes[i];
int s=get_cnt(a,t)-get_cnt(b,t)-get_cnt(a-b,t);
res=res*qmi(t,s)%p;
}
}
Lucas定理 复杂度与余数有关
#include<iostream>
using namespace std;
typedef long long LL;
LL qmi(LL a,LL b,LL p)
{
LL res=1%p;
while(b)
{
if(b&1) res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
LL C(LL a,LL b,LL p)
{
LL res=1;
for(LL i=1,j=a;i<=b;i++,j--)
{
res=res*j%p;
res=res*qmi(i,p-2,p)%p;
}
return res%p;
}
LL Lucas(LL a,LL b,LL p)
{
if(a<p&&b<p) return C(a,b,p);
return C(a%p,b%p,p)*Lucas(a/p,b/p,p)%p;
}
int main()
{
int n;
cin>>n;
while(n--)
{
LL a,b,p;
cin>>a>>b>>p;
cout<<Lucas(a,b,p)<<endl;
}
}
