蒟蒻太弱什么都不懂背个公式就假装自己懂了的样子

dalao原博
参考

逆元

定义

当求解公式：$(a/b)\%m $时，因b可能会过大

会出现爆精度的情况，所以需变除法为乘法：

设c是b的逆元，则有$b*c≡1(mod \ m)；$

则$(a/b)\%m = (a/b) \%m = (a/b) \times b \times c\%m =a \times c(mod \ m);$

即$a/b$的模等于$a \times b$的逆元的模；

求解方法

1. 扩展欧几里得

不难发现逆元的式子就是一个同余方程
$ax≡1( mod \ b)$
具体讲解见前一篇文章
这也是我最清楚的代码emmmmm代码见最后
复杂度：$O(logn)$；

2. 欧拉定理快速幂

在模为素数p的情况下，有费马小定理
$$
a^{p-1}=1（mod \ p）
$$

那么
$$
a^{p-2}=a^{-1}(mod \ p)
$$

也就是说a的逆元为$a^{p-2}$
而在模不为素数p的情况下，有欧拉定理
$$
a^{phi(m)} =1（mod \ m） (a⊥m)
$$

同理
$$
a^{-1}=a^{phi(m)-1}
$$
因此逆元x便可以套用快速幂求得了
$$
x=a^{phi(m)-1}
$$
PS:这种算法复杂度为O（log2N）在几次测试中，常数似乎较上种方法大
当模p不是素数的时候需要用到欧拉定理
$$
a^{phi(p)}≡1(mod\ p)\
a \times a^{phi(p)-1}≡1 (mod \ p)\
a^{-1}≡a^{phi(p)-1} (mod \ p)
$$

​

3. 线性递推

考虑到 $p=ki+r$，得到$ ki+r=0(mod \ p)$

移项：$r=−ki(mod \ p)$

同乘$1/r \times 1/i $ , $1/i=−k\times 1/r$

其中：$k=⌊p/i⌋，r=p\%i$

$i^{-1} \equiv -k \times r^{-1} (mod\ p)$

代入得 $i^{-1} \equiv -⌊p/i⌋ \times (p \mod i)^{-1} (mod \ p)$

由于$p\ mod \ i <i$所以可在$i^{-1}$之前求出$(p \ mod i)^{-1}$

放放代码（没几个自己敲的

代码

扩欧

#include <bits/stdc++.h>
#define N 100000+110
using namespace std;
int a,b,ans,sum,y,x,n;
void exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;}
    else
    {
         exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }

}
int main()
{
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
         exgcd(i,b,x,y);
         printf("%d\n",(x+b)%b);
         x=0;y=0;
    }



    return 0;
}

快速幂

ll ksm(ll x,ll y)
{
    ll sum=1;
    while(y)
    {
        if(y&1)sum=mult(sum,x)%mod;
        x=mult(x,x)%mod;
        y/=2;
    }
    return sum;
}
printf ("%lld\n", ksm(i, p-2, p) );

线性递推

  inv[1]=1;
  for(int i=2;i<=n;i++)
      inv[i]= (- mod/i *inv[mod % i]+mod)%mod;

卢卡斯定理

原blog

用处

主要是处理对于$C(n,m)\ mod\ p$时，p比较小而n，m较大的情况，模数太大反而适得其反

证明

首先需要证明

$$
C_p^i=\frac{p}{j}C_{p-1}^{i-1}\equiv0~~~(mod~p),(1<=i<=p-1)
$$
这个还比较好证明

$$
C_p^i=\frac{p!}{i!(p-i)!}=\frac{p}{i} \frac{(p-1)!}{(i-1)!(p-1-i+1)!}= \frac{p}{i} \frac{(p-1)!}{(i-1)!(p-i)!}=\frac{p}{j}C_{p-1}^{i-1}
$$
然后是二项式的性质（其实我不懂）

$$
(1+x)^p=C_p^01^p+C_p^1x^{2}+….+C_p^px^p=C_p^01^px^0+C_p^p1^0x^p=1+x^p
$$
接下来再需要证明
$$
C_a^b=C_{a_0}^{b_0}\cdot C_{a_1p}^{b_1p} \cdot C_{a_2p^2}^{b_2p^2}….
$$
首先我们令$a=lp+r,b=sp+j$

于是我们就需要证明$C_a^b=C_{lp}^{sp}\cdot C_{r}^{j}$

继续从二次项定理出发
$(1+x)^a=(1+x)^{lp} \cdot (1+x)^r$
然后展开$(1+x)^{lp}$
$$
(1+x)^{lp} \equiv ((1+x)^p)^l \equiv (1+x^p)^l
$$

$$
\therefore (1+x)^a \equiv (1+x^p)^l \cdot (1+x)^r
$$

观察项$x^b$的系数
$$
\because C_a^bx^b \equiv C_l^sx^{sp} \cdot C_r^jx^j
$$

$$
\therefore C_a^bx^b \equiv C_l^s \cdot C_r^jx^b
$$

$$
\therefore C_a^b\equiv C_l^s\cdot C_r^j \equiv C_{\lfloor \frac{a}{p} \rfloor}^{\lfloor \frac{b}{p} \rfloor}\cdot C_{a~mod~p}^{b~mod~p}
$$

上面的下取整是计算l and s，mod 是为了计算 r and j 得证

于是lucas定理内容如下
$$
lucas(n,m,p)=C(n \% p,m \% p) \times lucas(n/p,m/p,p)
$$
其中
$$
Lucas(x,0,p)=1
$$
于是就这样完了。。

总之背个结论就行

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+110;
ll n,m,fac[N],mod;
ll ksm(ll x,ll y)
{
    ll sum=1;
    while(y)
    {
        if(y&1)sum=sum*x%mod;
        x=x*x%mod;
        y/=2;
    }
    return sum;
}

ll c(ll x,ll y)
{
    if(y>x)return 0;
    return ((fac[x]*ksm(fac[y],mod-2))%mod*ksm(fac[x-y],mod-2)%mod);
}
ll lucas(ll x,ll y)
{
    if(!y)return 1;
    return c(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;
}
int main()
{
    int Case;
    scanf("%d",&Case);
    while(Case--)
    {
        scanf("%lld%lld%lld",&n,&m,&mod);
        fac[0]=1;
        for(int i=1;i<=mod;i++)fac[i]=(fac[i-1]*i)%mod;
        printf("%lld\n",lucas(n+m,n));

    }
    return 0;
}

终于码完了。。。