逆元

对于(a/b)%MOD这个式子，是不可以写成(a%MOD/b%MOD)%MOD，但是我们可以通过求b的逆元，转化成乘法运算

方程ax≡1(mod p),的解称为a关于模p的逆，当gcd(a,p)==1（即a，p互质）时，方程有唯一解，否则无解。

有如下几种求逆元的方式

1.递推求逆元逆元有这样一个公式：inv[i]=-p/i*inv[p%i]%p,inv[i]是i的逆元

这里稍微再拓展一下：

我们有时候会解决一个组合数取模的问题，那我们就可以先处理出阶乘，和阶乘的逆元

比如这道题

【题目】

Mr. Hu 又来让你帮忙解方程了。

方程是这样的：x1 + x1 + x3 + · · · + xn = m (xi ≥ 0 ∀1 ≤ i ≤ n)

Mr. Hu 希望你求出这个 n 元一次方程的整数解有多少个，因为解的个数有可能变得很大，所以 Mr. Hu只需要你输出解的个数取模于 mod。

【输入格式】
第 1 行，包含一个整数：T，表示询问个数
接下来 T 行，每行包含三个整数：n m mod
【输出格式】
输出 T 行，每行输出解的个数模对应 mod

【输入样例】

2 3 13

【输出样例】

【数据范围及约定】

样例中，解分别是：(3, 0),(2, 1),(1, 2),(0, 3)
• 对于 30% 的数据，1 ≤ n, m ≤ 6，mod = 108 + 7，T = 1
• 对于 70% 的数据，1 ≤ n, m ≤ 103，n + m ≤ mod ≤ 108 + 7，mod 是一个素数，1 ≤ T ≤ 100
• 对于余下 30% 的数据，1 ≤ n, m ≤ 103，n + m ≤ p, q ≤ 104，mod = p*q，p, q 是素数，1 ≤ T ≤ 103

简单分析一下，大概就可以看成是有m个小球放入n个盒子里，通过夹棍法我们知道答案是C（m+n+1-1,，n-1）

那我们就可以先处理出阶乘，再用O（1）的时间复杂度解决lalala

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
ll fac[maxn],invfac[maxn];
ll C(int n,int m,int p)
{
    return fac[n]*invfac[n-m]%p*invfac[m]%p;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        fac[0]=invfac[0]=fac[1]=invfac[1]=1;
        for(int i=2;i<=m+n;i++)
          invfac[i]=-p/i*invfac[p%i]%p;
        for(int i=2;i<=m+n;i++) 
        {
            fac[i]=(fac[i-1]*i%p+p)%p;//阶乘
            invfac[i]=(invfac[i-1]*invfac[i]%p+p)%p;
        }
        printf("%I64d
",C(m+n-1,n-1,p));
    }
}

逆元阶乘

2.快速幂求阶乘

ax≡1(mod p)，我们知道a与p互质，根据费马小定理，我们知道a的逆元就是a^（p-2）

那么一个快速幂就可以解决，但是如果p太大，这个算法就。。。

（仍然是上面那道题的代码）

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
ll fac[maxn];
ll quick_pow(ll a,ll x,ll mod)
{
    ll ans=1,t=a;
    while(x)
    {
        if(x%2==1) ans=ans*t%mod;
        t=t*t%mod;
        x=x>>1%mod;
    }
    return ans%mod;
}
ll C(int n,int m,int p)
{
    return fac[n]*quick_pow(fac[n-m],p-2,p)%p*quick_pow(fac[m],p-2,p)%p;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        fac[0]=fac[1]=1;
        //for(int i=2;i<=m+n;i++)
          //invfac[i]=-p/i*invfac[p%i]%p;
        for(int i=2;i<=m+n;i++) 
        {
            fac[i]=fac[i-1]*i%p;
        
        }
        printf("%I64d
",C(m+n-1,n-1,p));
    }
}

快速幂逆元

3.扩欧求逆元

ax≡1(mod p)，也就是ax-py=1

这个算法的好处是不用保证p一定是个质数，只要与a互质即可

（仍然是上面那道题的代码）

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
ll exgcd(ll a,ll &x,ll b,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll x2,y2;
    ll gcd=exgcd(b,x2,a%b,y2);
    x=y2;
    y=x2-a/b*y2;
    return gcd;        
}
ll C(int n,int m,int p)
{
    ll mm=1,nn=1;
    for(int i=n;i>m;i--)mm=mm*i%p;
    for(int i=1;i<=n-m;i++) nn=nn*i%p;
    ll y,inv;
    ll gcd=exgcd(nn,inv,p,y);
    inv/=gcd;
    mm=(mm*inv%p+p)%p;
    return mm;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        printf("%I64d
",C(m+n-1,n-1,p));
    }
}

扩欧逆元

至于什么模数又不是质数又不和a互质，好像是还要开个数组存个啥啥的，emm现在我还不会la