AcWing 886. 求组合数 II
原题链接
简单
作者:
kRYST4L
,
2023-05-27 17:43:57
,
所有人可见
,
阅读 135
求组合数 II($a<=10^5,b<=10^5$,预处理的方法)
- 时间复杂度为$O(nlogn)$
- 肯定不能用组合数I的递推公式了,不然时间复杂度为$O(10^{10})$,肯定TLE
- 组合数II的转换公式为:$C_{a}^{b}=\frac{a!}{(a-b)!*b!}=fact[a]\times infact[a-b]\times infact[b]$
- 上述公式中($fact[a]$表示$a!$,$infact[b]$表示$b!$的逆元)
- 为什么可以这么转换,去搜下取模的运算法则就ok
- 这题为什么可以用费马小定理:因为mod=1e9+7是质数,只要$i!$不等于mod,两者肯定互质
我从这道题学到了什么
- 性质1:如果x是a的逆元,y是b的逆元,即$ax\equiv1,by\equiv1$,所以$abxy\equiv1$,即xy是ab的逆元,说明要求ab的逆元,直接将a的逆元和b的逆元相乘即可
infact[i]=(LL)infact[i-1]*qmi(i,MOD-2,MOD)%MOD;
这行代码就是根据性质1来的
- 证明如下:
- $(i!)^{-1}\equiv ((i-1)!)^{-1}\times (i)^{-1}\equiv ((i-1)!)^{-1}\times (i)^{p-2} $就是上面那行代码
- 其实这行代码
infact[i]=(LL)infact[i-1]*qmi(i,MOD-2,MOD)%MOD;
- 我觉得这样写更好理解
infact[i]=(LL)qmi(fact[i],MOD-2,MOD)%MOD;
,因为$(i!)^{-1}\equiv (i!)^{p-2}$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010,MOD=1e9+7;
LL fact[N],infact[N];//fact[i]代表i的阶乘,ifact[i]代表i的阶乘的逆元
int n;
int qmi(int a,int b,int p)
{
LL res=1;
while(b)
{
if(b&1) res=(LL)res*a%p;
a=(LL)a*a%p;
b>>=1;
}
return res;
}
int main()
{
cin>>n;
fact[0]=infact[0]=1;
for(int i=1;i<N;i++)
{
fact[i]=(LL)fact[i-1]*i%MOD;//乘的时候记得都要转成LL,不然会爆
infact[i]=(LL)infact[i-1]*qmi(i,MOD-2,MOD)%MOD;//打卡会详细说明
}
while (n -- )
{
int a,b;
cin>>a>>b;
cout<<(LL)fact[a]*infact[a-b]%MOD*infact[b]%MOD<<endl;//中间取一次模是为了防止爆longlong,三个数直接相乘再取模可能会爆
}
}