题解
两个题都是预处理
I是组数多,a,b范围小,预处理所有的$C_{a}^{b}$
II是组数少,a,b范围大,预处理所有的阶乘
$$C_{a}^{b}=\frac{a!}{b!(a-b)!}$$
我们发现最后要%1e9+7,可是这是个分式,取模运算没有除法法则,必须要求逆元,所以我们不仅要求出所有的jie[i]
,还要求出所有的injie[i]
($i!$模1e9+7的逆元)
逆元的阶乘
设a
的逆元为$a^{-1}$,乘的逆元为$b^{-1}$,那么ab
的逆元是多少呢?
$$aa^{-1}≡1(\%\ mod)\ ,\ bb^{-1}≡1(\%\ mod)$$
$$(ab)(a^{-1}b^{-1})≡1(\%\ mod)$$
我们可以得到,ab的逆元
恰恰就是a的逆元×b的逆元
。
所以得到injie[i]=injie[i-1]*niyuan(i)
的递推式。
代码——exgcd()版本
#include<iostream>
using namespace std;
typedef long long intt;
const intt N=1e5+10;
const intt mod=1e9+7;
intt jie[N],injie[N];
typedef pair<intt,intt> II;
II exgcd(intt a,intt b){
if(b==0) return {1,0};
else{
II temp=exgcd(b,a%b);
return {(temp.second+mod)%mod,(temp.first-a/b*temp.second+mod)%mod};
//如果不mod的话会很大溢出或者为负数 不太清楚x,y mod后为什么没事
//目前只能用“ax+ym≡gcd()(mod 1e9+7)这个式子是在取模的环境下 那么遵循乘法和加法的取模法则”来解释
}
}
void preprocess(){
jie[0]=1,injie[0]=1;
jie[1]=1,injie[1]=1;
II temp;
for(intt i=2;i<=N;i++){
jie[i]=(jie[i-1]*i)%mod;
temp=exgcd(i,mod);//求i在模mod时的逆元
injie[i]=injie[i-1]*temp.first%mod;
}
}
int main(void){
intt n,a,b;
cin>>n;
preprocess();
for(int i=0;i<n;i++){
cin>>a>>b;
cout<<jie[a]*injie[b]%mod*injie[a-b]%mod<<endl;
}
}
代码——快速幂
#include<iostream>
using namespace std;
typedef long long intt;
const intt N=1e5+10;
const intt mod=1e9+7;
const intt M=1e9+5;
intt jie[N],injie[N];
intt r[30];
typedef pair<intt,intt> II;
intt qkm(intt x){
r[0]=x;
for(int i=1,inspect=2;inspect<=M;i++,inspect=inspect<<1){
r[i]=r[i-1]*r[i-1]%mod;
}
intt product=1;
for(int i=0,inspect=1;inspect<=M;i++,inspect=inspect<<1){
if((M>>i)&1) product=product*r[i]%mod;
}
return product;
}
void preprocess(){
jie[0]=1,injie[0]=1;
jie[1]=1,injie[1]=1;
for(intt i=2;i<=N;i++){
jie[i]=(jie[i-1]*i)%mod;
injie[i]=injie[i-1]*qkm(i)%mod;//qkm(i)求i在%1e9+7下的逆元
}
}
int main(void){
intt n,a,b;
cin>>n;
preprocess();
for(int i=0;i<n;i++){
cin>>a>>b;
cout<<jie[a]*injie[b]%mod*injie[a-b]%mod<<endl;
}
}