👉更好的阅读体验
关于求组合数 II的一些疑问 蒟蒻一枚,第一次用markdown,排版不清楚,望见谅
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:那么为什么非要转换成乘法逆元呢?
不能使用除法,显然数学家们是不能忍受这种局面的,他们扔出了“逆元”来解决这个问题。
证明:
开始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 的乘法逆元。
费马小定理:若 p 是质数,整数b不是p的倍数,则 b^(p−1)≡1(modp).
我们可以将式子变形:b⋅b^p−2≡1(modp),所以 binv=b^p−2,结合快速幂模板可求解
Q4:为什么在求逆元的时候mod后还要mod
其实这可以参照模运算的乘法法则
因为在乘法过程中,答案会非常大,而mod多一次并不会改变最终的答案,可以举个小一点的例子,我太懒了,这里就不举了只是在过程中把量减小了,不会在计算过程中超出数据范围而出现什么奇怪的答案
代码
#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;
}
这道题我开始一直没想清楚为什么可以用逆元,想了好久也没想到,一个一个查才发现
如果还有什么问题可以一起交流,如果对你有帮助,希望能点个赞
写的很好。
赞