社区讨论

求助qwq 求组合数的乘法逆元时出现了问题

P1641[SCOI2010] 生成字符串参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6we0ir
此快照首次捕获于
2025/11/20 11:54
4 个月前
此快照最后确认于
2025/11/20 11:54
4 个月前
查看原帖
这是全WA的代码
CPP
ll fac(ll x){
    ll mul = 1;
    for(int i = 2; i <= x; i++) mul = (mul * i % mod) % mod;
    return mul;
}

ll C(ll n, ll m){
    ll j1 = fac(n);
    ll j2 = inv(fac(m));
    ll j3 = inv(fac(n - m));
    return (j1 * j2 * j3) % mod;
}
然后 这是AC的代码
CPP
ll fac(ll x){
    ll mul = 1;
    for(int i = 2; i <= x; i++) mul = (mul * i) % mod;
    return mul;
}

ll C(ll n, ll m){
    ll j1 = fac(n);
    ll j2 = fac(m);
    ll j3 = fac(n - m);
    j2 = (j2 * j3) % mod;
    return j1 * inv(j2) % mod;
}
一个是将分母上的两项分开 求逆元再相乘 一个是将两项先相乘合并起来 再求逆元
蒟蒻想问的是 是不是乘法逆元不满足分配律(大雾 不知道叫什么律) 以及乘法逆元满足什么规律 不满足什么规律???qwq

回复

4 条回复,欢迎继续交流。

正在加载回复...