前备知识点
这道题集合了很多的知识点,快速幂 + 乘法逆元 + 组合数,如果一个知识点断了层,就会卡很长时间,比如说我
快速幂
快速幂的思想是指数减半,底数翻倍,这样不仅可以减少循环的次数,最后的结果也不会改变
乘法逆元
定义:若存在正整数a,b,p, 满足ab = 1(mod p), 则称a 是b 的乘法逆元, 或称b 是a 的乘法逆元。b ≡ a-1 (mod p),a ≡ b-1 (mod p)
举例:在模7 意义下,3 的乘法逆元是5, 也可以说模7 意义下5的乘法逆元是3
如果b与模数n互质,当模数n为质数时,我们可以直接用公式x = b^n−2^ % n
来求b的乘法逆元
核心思想:可以在运算除时,转化为乘法
比如说在求(a/b)%p,除法会不好进行计算,我们就可以通过计算出b的乘法逆元k,k = b^-1(mod p),然后让a * k % p,这个结果和(a/b)%p是一样的
然后,我们就把除法转化为了乘法,简而言之,除以一个数,就等于乘以这个数的逆元
算法推导
$C^b_a=a!/b!(a−b)!$
因为再求除法的时候不好求,所以我们要想办法转化为除法,因为除以一个数,就等于乘以这个数的逆元,所以我们就想到了逆元,然后再看逆元用那种方式做
费马小定理:如果p是质数,整数a不是p的倍数的话: $a^p-1 % p ≡ 1$
因为a,b的范围是1≤b≤a≤10^5,mod = 1e9 + 7,mod是一个质数,并且b和a-b的范围不可能是mod的倍数,所以是可以用快速幂 + 费马小定理来做的
也就是b的逆元 = $b^{mod-2}$%mod, 传入参数b,mod-2,mod即可
精度转化
因为$a$是底数,$mod - 2$特别大,所有a会爆int,所以用long t = a;就可以避免在多个地方进行转化了
代码
import java.util.Scanner;
public class Main{
static int N = 100010, mod = 1000000007;
static long[] fact = new long[N]; //阶乘
static long[] infact = new long[N]; //逆元de阶乘 x = b^n-2 (mod n)
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++)
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
while(n-- > 0)
{
int a = in.nextInt();
int b = in.nextInt();
System.out.println(fact[a] * infact[a - b] % mod * infact[b] % mod);
}
}
private static long qmi(int a, int b, int p)
{
long res = 1;
long t = a; //相当于把int的类型转化为了long类型,因为快速幂的思想是指数减半,底数翻倍
while(b != 0)
{
if((b & 1) != 0) res = res * t % p;
t = t * t % p;
b >>= 1;
}
return res;
}
}