当前位置：网站首页>没那么大的组合数

没那么大的组合数

2022-07-17 06:45:00 【2020100XWH】

直接计算

再大且p 1e5这样的话配合卢卡斯处理

线性求逆元

p-2逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
int p,inv[N],a[N];
void invv()
{
    inv[1]=1;
    for(int i=2;i<=N;++i)
    {
        inv[i]=(p-(p/i))*inv[p%i]%p;
    }
    return ;
}
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
ll mm(ll x)
{
    return qpow(x,p-2);
}
ll c(ll n,ll m)
{
    ll ans=1;
    for(ll i=1,j=n-m+1;i<=m;++i,++j)
    {
        ans=(ans*mm(i))%p;
        ans=(ans*j)%p;
    }
    return ans;
}
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,m;
        cin>>n>>m>>p;
        cout<<c(n,m)<<"\n";
    }
    return 0;
}

原网站

版权声明
本文为[2020100XWH]所创，转载请带上原文链接，感谢
https://blog.csdn.net/xuwnehao/article/details/125707925

边栏推荐

猜你喜欢

随机推荐