逆元求组合数

ゝ一纸荒年。 2023-07-17 12:42 32阅读 0赞

## **逆元简介** ##

**同余符号 ≡**  
先bb一下 ≡，这个符号有三个意思，再这里用到的意思为“同余符号”。[≡ 的介绍][Link 1]  
两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余  
记作a≡b(mod m)  
读作a同余于b模m，或读作a与b关于模m同余。  
比如26≡14(mod 12)。  
**什么是逆元**  
如果一个线性同余方程 ax ≡ 1(mod b) ，则 x 称为 a mod b 的逆元.  
**逆元的含义**  
模b意义下，1个数a如果有逆元x，那么除以a相当于乘以x。  
也就是(a/b)%p=(a*x)%p=(a%p)*(b%p)%p

那么问题来了，这逆元有啥用吗，这个问题问的好啊  
如果我们要求一个组合数C(n,m)%p=(n!/(n-m)!\*m!)%p,但是取模的性质对于除法不适用啊。  
![在这里插入图片描述][20200321141135906.png]  
但当这个n和m很大时又不得不取模，不取模就会溢出。所以就可以用逆元来把乘法代替除法。

## 怎么求逆元 ##

**暴力O( P)求逆元**  
先举这个最简单最暴力的方法，这样便于理解逆元。具体思路就是枚举1~p-1，检查是否有符合条件的a\*x=1(mod p)。时间复杂度为O（P）。

#include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    { 
        int a,p;
        cin>>a>>p;
        for(int x=1;x<p;x++){ 
            if(x*a%p==1) { 
                printf("%d\n",x);
                break;
            }
        }
        return 0;
    }

**扩展欧几里得法**  
给定模数p，求a的逆元相当于求解ax=1(mod p)  
这个方程可以转化为ax-py=1  
然后套用求二元一次方程的方法，用扩展欧几里得算法求得一组x0,y0和gcd (最大公约)  
检查gcd是否为1  
gcd不为1则说明逆元不存在 ，若为1，则把x0调整到0~m-1的范围中即可  
（ ①：extgcd 目的 求 x ,y ； ②：逆元 目的 求 x ）  
一个数有逆元的充分必要条件是gcd(a,n)=1，如果gcd(a,n)>1,则不存在逆元

int exgcd(int a,int b,int &x,int &y)
    { 
        if(b==0) { 
            x=1,y=0;
            return a;
        }
        int r = exgcd(b,a%b,x,y);
        int t = x;
            x = y;
            y = t - a/b*y;
        return r;
    }

## **快速幂法** ##

这个要运用 费马小定理 ：  
![在这里插入图片描述][20200322222005889.png]  
再看看推导过程：  
![在这里插入图片描述][20200322222056421.png]  
由以上推导就可以通过求一个幂运算很简单的求出逆元辽。

上一个代码，具体功能就是求n和m的组合数mod1e9+7

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const ll Mod=1e9 + 7;
    ll fac[100010];//存阶乘 
    ll inv[100010];//存逆元 
    
    ll quick(ll a,int b)//快速幂算法 
    { 
    	ll ans=1;
    	while(b)
    	{ 
    		if(b&1)ans=(ans*a)%Mod;
    		a=a*a%Mod;
    		b>>=1;
    	}
    	return ans;
    }
    
    void getfac()
    { 
    	fac[0]=inv[0]=1;
    	for(int i=1;i<=100000;i++)
    	{ 
    		fac[i]=fac[i-1]*i%Mod;
    		inv[i]=quick(fac[i],Mod-2); 
    	}
    }
    
    ll getans(ll n,ll m)
    { 
    	return fac[n]*inv[n-m]%Mod*inv[m]%Mod;
    }
    
    int main()
    { 
    	getfac();//初始化
    	
    	ll n,m;
    	while(cin>>n>>m)
    	{ 
    		ll ans=getans(n,m);
    		cout<<ans<<endl;
    	} 
    }

## **Lucas定理** ##

**对于大组合数取模，n,m不大于10 ^ 5的话，用逆元的方法，可以解决。对于n,m大于10 ^ 5的话，那么要求p<10 ^ 5，这样就是Lucas定理了，将n,m转化到10^5以内解。**  
Lucas定理是用来求 c(n,m) mod p，p为素数的值。  
C(n,m)%p=C(n/p,m/p)\*C(n%p,m%p)%p  
也就是Lucas(n,m)%p=Lucas(n/p,m/p)\*C(n%p,m%p)%p  
求上式的时候，Lucas递归出口为m=0时返回1，原因是因为**Lucas(a,0,q)=1;**  
**模板：**

#include <cstdio> 
    #include <iostream> 
    #include <cmath> 
    #include <cstring> 
    #include <algorithm> 
    using namespace std;  
    #define maxn 100010 
    typedef long long LL;  
    LL m,n,p;  
    LL Pow(LL a,LL b,LL mod)  
    {   
        LL ans=1;  
        while(b)  
        {   
            if(b&1)ans=(ans*a)%mod;
            a=a*a%mod;
            b>>=1;
        }  
        return ans;  
    }  
    LL C(LL n,LL m)  
    {   
        if(n<m)  
            return 0;  
        LL ans=1;  
        for(int i=1;i<=m;i++)  
        {   
            ans=ans*(((n-m+i)%p)*Pow(i,p-2,p)%p)%p;  
        }  
        return ans;  
    }  
    LL Lucas(LL n,LL m)  
    {   
        if(m==0)  
            return 1;  
        return (Lucas(n/p,m/p)*C(n%p,m%p))%p;  
    }  
    int main()  
    {   
        int t;  
        scanf("%d",&t);  
        while(t--)  
        {   
            scanf("%lld%lld%lld",&n,&m,&p);  
            printf("%lld\n",Lucas(n,m));  
        }  
        return 0;  
    }

[Link 1]: https://zhidao.baidu.com/question/1737600378739355227.html
[20200321141135906.png]: /images/20230528/b4079a10b43a4f739a7aa7478f9f9ccf.png
[20200322222005889.png]: /images/20230528/7abc92cdc7ff4278bf509528d5e3fb7b.png
[20200322222056421.png]: /images/20230528/f3fc622dc88c45158f080b8fba3f1526.png