模板

（前置芝士）

P1226 【模板】快速幂 | 取余运算

目的：

顾名思义，快速求解乘方。

实现：

挺好写的。

题目传送门

代码

P3811 【模板】乘法逆元

开long long!!

定义：

若 \(a * x\equiv1\pmod b\) ，且 \(a\) 与 \(b\) 互质，那么就能定义 \(x\) 是 \(a\) 在模 \(p\) 意义下的逆元，记为 \(a^{-1}\) 。

其实就是若一个数在模 \(p\) 意义下，

原来我不理解的地方是为什么一个整数的逆元为什么也是整数，当时是因为忽视了是在模 \(p\) 意义下的。在听了正睿的网课后又有了更深一步的理解，可以用群论证明。

目的：

一般用于求 \(\frac{a}{b} \pmod p\) 的值（ \(p\) 通常为质数），是解决模意义下分数数值的必要手段。

实现：

1. 显然的，既然是求解 \(a * x\equiv1\pmod b\) 这个式子，那么就可以用扩展欧几里得求解。可以用于求解模数 \(p\) 很大或者 \(p\) 不是质数时的逆元。

代码

2. 可以用费马小定理借助快速幂求解

若 \(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\) 必须为质数。

代码

3. 对于 \(1\) ~ \(n\) 内所有数的逆，可以用递推法线性求解。

   首先无论模数 \(p\) 为何值，\(i=1\) 的逆都为 \(1\)。下面求 \(i>1\) 时的逆。

   1. 设 \(p/i=k\)，余数是 \(r\)。则有 \(k \cdot i+r \equiv0\pmod p\)。

   2. 两边同乘 \(i^{-1} \cdot r^{-1}\)，得到 \(k \cdot r^{-1}+i^{-1}\equiv0\pmod p\)

   3. 由于要求的是 \(i^{-1}\) 所以移项，得到 \(i^{-1}\equiv -k \cdot r^{-1} \pmod p\)，即 \(i^{-1}\equiv -p/i \cdot r^{-1} \pmod p\)。

   4. 但到这里还没结束，为了保证 \(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;。

代码

4. 可以用递推线性计算出 \(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\) 计算。