模板
（前置芝士）
P1226 【模板】快速幂 | 取余运算
目的：
顾名思义，快速求解乘方。
实现：
挺好写的。
P3811 【模板】乘法逆元
开long long!!
定义：
若 \(a * x\equiv1\pmod b\) ，且 \(a\) 与 \(b\) 互质，那么就能定义 \(x\) 是 \(a\) 在模 \(p\) 意义下的逆元，记为 \(a^{-1}\) 。
其实就是若一个数在模 \(p\) 意义下，
原来我不理解的地方是为什么一个整数的逆元为什么也是整数，当时是因为忽视了是在模 \(p\) 意义下的。在听了正睿的网课后又有了更深一步的理解，可以用群论证明。
目的：
一般用于求 \(\frac{a}{b} \pmod p\) 的值（ \(p\) 通常为质数），是解决模意义下分数数值的必要手段。
实现：
- 显然的，既然是求解 \(a * x\equiv1\pmod b\) 这个式子，那么就可以用扩展欧几里得求解。可以用于求解模数 \(p\) 很大或者 \(p\) 不是质数时的逆元。
- 可以用费马小定理借助快速幂求解
若 \(p\) 为质数，\(a\) 为正整数，且 \(a\) , \(p\) 互质。则有 \(a^{p-1}\equiv1\pmod p\) 。
既然 \(a^{p-1}\) 在模 \(p\) 意义下等于 \(1\)，那显然 \(a \times a^{p-2} \equiv1\pmod p\) ，所以 \(a^{p-2}\) 是 \(a\) 的逆元。那么就可以用快速幂求解，需要的注意的是 \(p\) 必须为质数。
-
对于 \(1\) ~ \(n\) 内所有数的逆，可以用递推法线性求解。
首先无论模数 \(p\) 为何值，\(i=1\) 的逆都为 \(1\)。下面求 \(i>1\) 时的逆。
-
设 \(p/i=k\)，余数是 \(r\)。则有 \(k \cdot i+r \equiv0\pmod p\)。
-
两边同乘 \(i^{-1} \cdot r^{-1}\)，得到 \(k \cdot r^{-1}+i^{-1}\equiv0\pmod p\)
-
由于要求的是 \(i^{-1}\) 所以移项，得到 \(i^{-1}\equiv -k \cdot r^{-1} \pmod p\)，即 \(i^{-1}\equiv -p/i \cdot r^{-1} \pmod p\)。
-
但到这里还没结束，为了保证 \(i^{-1}>0\) 所以在等式右边加上 \(p\)
,由于 \(p \mod p=0\)，所以答案不变。得到 \(i^{-1}\equiv (p-p/i) \cdot r^{-1} \pmod p\)，即inv[i]=(p-p/i)*inv[p%i]%p;。
-
- 可以用递推线性计算出 \(1\) ~ \(n\) 的阶乘的逆。
首先需要先单独计算出 \(n\) 的阶乘的逆。那么\((n-1)!^{-1}=n!^{-1} \times n\)，即 fnv[i-1]=fnv[i]*1ll*i%p;。
求组合数
目的：
求 \(C_n^m\)，首先先预处理 \(1\) ~ \(n\) 的阶乘和阶乘的逆，然后根据公式 \(C_n^m=\frac{n!}{m!(n-m)!}\) 求解即可。需要提前判断一下 \(n\) 是否小于 \(m\)， 若小于则返回 \(0\)。
实现：
代码：
long long ksm(long long a,int b)
{
long long ans=1;
while(b)
{
if(b&1)
{
ans=(a*ans)%p;
}
a=(1ll*a*a)%p;
b>>=1;
}
return ans;
}
void init()
{
fac[0]=1;
for(int i=1;i<=n;i++)
{
fac[i]=fac[i-1]*1ll*i%p;
}
fnv[n]=ksm(fac[n],p-2);
for(int i=n;i>0;i--)
{
fnv[i-1]=fnv[i]*1ll*i%p;
}
}
long long C(int nn,int mm)
{
if(nn<mm) return 0;
return ((fac[nn]*fnv[mm])%p)*fnv[nn-mm]%p;
}
二项式定理
目的：
求解形如 \((x+y)^n\) 的式子。
实现：
利用公式 \((a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i\) 计算。