886. 求组合数 II

题目

给定 n 组询问，每组询问给定两个整数 a，b，请你输出 $C_b^amod(10^9+7)$ 的值。

输入格式
第一行包含整数 n。接下来 n 行，每行包含一组 a 和 b。

输出格式共 n行，每行输出一个询问的解。

数据范围 $1≤n≤10000$,$1≤b≤a≤105$
输入样例：

1
2
3
4
3
3 1
5 3
2 2

输出样例：

1
2
3
3
10
1

题解

Q1：明明是除法为什么要特意转换成乘法

那是因为这道题目最后是要求余的，模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a _ b) % p = (a % p _ b % p) % p
但对于除法却不成立，即(a / b) % p 不等于 (a % p / b % p) % p 。

Q2：那么为什么非要转换成乘法逆元呢？

不能使用除法，显然数学家们是不能忍受这种局面的，他们扔出了“逆元”来解决这个问题。

证明：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
开始a/b≡m(modp) -------①

假设存在 binv 满足a⋅binv≡x(modp)-------②

①②式两边同乘一个 b

得到

a≡bx(modp)----- ③

a⋅binv⋅b≡bx(modp)------④

根据模运算减法性质将两式相减④-③得 a(binv⋅b−1)≡0(modp)

因为我们在找b得乘法逆元，所以a的值任意，所以式子相当于 binv⋅b−1≡0(modp)

即 binv⋅b≡1(modp)
哎，binv是b的逆元呀（x 在模运算的乘法中等同于 1/b, 这就是逆元的意义）
所以我们只需要求b的逆元即可

Q3 所以逆元要怎么求呢？(k!)(−1)≡(k - 1)!(-1)^(p−2)是哪里来的？ (-1)是逆元!!

这里其实是有个小技巧的，因为 mod 是 1e9 +7，其实是一个非常大的质数，我们知道质数的因子只有 1 和其本身，所以 2~1e9 + 6 其实都是与 1e9 + 7 是互质
根据在 快速幂求逆元

我们知道若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡ax(modm)，则称 x 为 b 的模 m 乘法逆元，记为 $b^{−1}(modm)$。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，$b^{(m−2)}$ 即为 b 的乘法逆元。
以为 2~1e9 + 6 其实都是与 1e9 + 7 是互质的，所以根据小费马定理可以换算出$b^{(m−2)}$ 即为 b 的乘法逆元。

1
2
3
费马小定理：若 p 是质数，整数b不是p的倍数，则 b^(p−1)≡1(modp).

我们可以将式子变形：b⋅b^p−2≡1(modp)，所以 binv=b^p−2，结合快速幂模板可求解

Q4：为什么在求逆元的时候 mod 后还要 mod

其实这可以参照模运算的乘法法则
因为在乘法过程中，答案会非常大，而 mod 多一次并不会改变最终的答案，可以举个小一点的例子，我太懒了，这里就不举了只是在过程中把量减小了，不会在计算过程中超出数据范围而出现什么奇怪的答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int fact[N];
int infact[N];

int qmi(int a, int b, int m)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % mod;

        b >>= 1;

        a = (LL)a * a % mod;
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        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[b] % mod * infact[a - b] % mod << endl;
    }

    return 0;
}