AcWing 886. 求组合数 II-数论-C++

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 886. 求组合数 II-数论-C++ 原题链接简单

作者：

码 , 2020-10-06 22:26:39 , 所有人可见 , 阅读 7880

87

29

题型:求组合数
$C_a^b=\frac{a!}{b! (a-b)!}=a! \ast b!^{-1} \ast (a-b)!^{-1}$
$b!^{-1}与(a-b)!^{-1}如何求?$

利用快速幂求逆元
传送门

$b!^{-1}=((b-1)!b)^{-1}=(b-1)!^{-1} \ast b^{-1} - ①\\\\ b^{-1}=b^{1e9+5}(根据费马小定理) - ②\\\\由①②得b!^{-1}=(b-1)!^{-1} \ast b^{1e9+5}=(b-1)!^{-1} \ast b^{(mod-2)}$

∵mod=1e9+7是质数,所以2~1e9+6与1e9+7互质,所以可以使用费马小定理来求解逆元,逆元通过快速幂求解

快速幂求组合数 $\quad O(a \ast log(mod))$

#include<iostream>
using namespace std;
const int mod=1e9+7,N=1e5+10;
typedef long long LL;
long long fac[N],infac[N];
int quick_pow(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    int n;
    fac[0]=infac[0]=1;
    for(int i=1;i<=1e5;i++)
    {
        fac[i]=fac[i-1]*i%mod;
        infac[i]=(LL)infac[i - 1] * quick_pow(i,mod-2,mod)%mod;
    }
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(LL)fac[a] * infac[b] % mod * infac[a - b] % mod<<endl;
    }
}

$\color{brown}{喜欢题解的话,欢迎点赞、收藏、关注(三连)喔,如有什么疑问,欢迎评论下方指出}$

37 评论

Touper 2024-01-03 19:30

不应该是阶乘的逆元吗？为什么是逆元的阶乘

Touper 2024-01-03 19:56

for(int i=1;i<N;i++){
fact[i]=(ll)fact[i-1]*i%mod;
infact[i]=qmi(fact[i],mod-2,mod)%mod;
}

Touper 2024-01-03 19:57

写成这个样子更容易理解一些，我觉得

jack_152 2024-01-17 09:38

我也这么觉得

Mateogic 11个月前

我也这么觉得

明天堂 9个月前

点了

神崎日照 6个月前回复了 Touper 的评论

和阶乘一样可以写成递推形式，不用每次都从头算，不过快速幂复杂度不高，这么写应该也没问题

tool04 4个月前

我就寻思他们怎么都那样写

aushiro 2023-10-11 20:01

一些思考和尝试，希望可以帮到大家，看了一圈没有这样做的

// 不能通过#define int long long 直接简单省事
// 中间过程要加上(LL) 来处理不然最后会W/A
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int mod = 1e9 + 7;
const int N = 100010;
typedef long long LL;

int n;
int fact[N], infact[N];

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

LL C(int a, int b)
{
    int f_a = 1, f_b = 1, f_ab = 1;
    //在每个处理步骤上都要加(LL)否则会W/A
    for (int i = 1; i <= a; i ++) f_a = (LL)f_a * i % mod;
    for (int i = 1; i <= b; i ++) f_b = (LL)f_b * i % mod;
    for (int i = 1; i <= a - b; i ++) f_ab = (LL)f_ab * i % mod;
    //这种方法由于没有进行预处理，在处理多个数据是会大量重复计算导致TLE

    return (LL) f_a * qmi(f_b, mod - 2) % mod * qmi(f_ab, mod - 2) % mod;
}

signed main()
{
    scanf("%d", &n);

    fact[0] = infact[0] = 1;

    for (int i = 1; i < N; i ++) 
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = qmi(fact[i], mod - 2);//事实证明infact先阶乘后取逆元仍正确
    }
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%lld\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
        // printf("%lld\n", C(a, b));
    }

    return 0;
}