Chat Group gym101775A(逆元，组合数)

传送门：Chat Group（gym101775A）

题意：一个宿舍中又n个人，最少k（k >= 3）个人就可以建一个讨论组，问最多可以建多少个不同的讨论组。

思路：求组合数的和，因为涉及除法取余，所以要求逆元来解题。

虽然之前看到过有关逆元的知识，但是一直没有弄明白逆元的应用。嗯~~挖下的坑终于把自己给坑了。这次认栽！！

最终的结果是：C(n,k)+C(n,k+1)+.......+C(n,n) = 2^n - ( C(n,0) + C(n,1) + C(n,2) + ......+C(n,k-1)

(a / b)%mod = a % mod *(b关于模mod的逆元);

复习逆元相关知识：Click hear

代码：

费马小定理求逆元法：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+;

const int maxn = 1e5;

typedef long long ll;

int n,k;

ll qpow(ll a,ll b)

{

    ll res = ;

    while(b)

    {

        if(b&)

            res = res*a%MOD;

        a = a*a%MOD;

        b>>=;

    }

    return res;

}

int main()

{

    int T,cnt = ;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&k);

        ll c = ;

        ll sum = ;

        for(int i = ; i<=k-; i++)

        {

            c = ((c*(n-i+)%MOD)*qpow(i,MOD-))%MOD;

            sum = (sum + c)%MOD;

        }

        ll M = qpow(,n) - ;

        printf("Case #%d: %lld\n",++cnt,(M - sum + MOD)%MOD);//将结果转为正数

    }

    return ;

}

线性求逆元：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9+;

const int maxn = 1e5;

typedef long long ll;

int n,k;

ll qpow(ll a,ll b)

{

    ll res = ;

    while(b)

    {

        if(b&)

            res = res*a%MOD;

        a = a*a%MOD;

        b>>=;

    }

    return res;

}

ll inv[maxn];

void getInv()

{

    inv[] = ;

    for(int i = ; i<maxn; i++)

    {

        inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;

    }

}

int main()

{

    int T,cnt = ;

    scanf("%d",&T);

    while(T--)

    {

        getInv();

        scanf("%d%d",&n,&k);

        ll c = ;

        ll sum = ;

        for(int i = ; i<=k-; i++)

        {

            c = (c*(n-i+)%MOD*inv[i])%MOD;

            sum = (sum + c)%MOD;

        }

        ll M = qpow(,n) - ;

        printf("Case #%d: %lld\n",++cnt,(M - sum + MOD)%MOD);

    }

    return ;

}

巴特西

Chat Group gym101775A(逆元，组合数)

最新文章

热门文章