# 模逆元與應用

如有錯誤請告知，感謝><

## 模逆元定義

在乘法中，我們定義$a$的倒數為$a^{-1}$，即$a\times a^{-1}=1$

對任意正整數$a$，取模($mod\space p$)後的倒數定義成$a$的模倒數或稱模逆元(在$mod\space p$的情況下)

即$a\times a^{-1}=1(mod\space p)$，此時的$a^{-1}$為模逆元

但對於任意的$a$、$p$，其不一定有模逆元素，若$gcd(a,p)\space !=1 \space, a\space mod\space p$即無模逆元

## 模逆元算法
### 根據費馬小定理:
#### 若p為質數，對任意正整數$a$，$(a^{p-2}mod\space p)$是$a$在$[1, P-1]$區間的唯一乘法反元素

所以我們可以搭配快速冪在$O(log\space p)$內算出模逆元

## 線性模逆元

若我們想要求 $1, 2, 3, \dots n$ 的模逆元，一個一個套用費馬小定理顯然有點慢，以下介紹一個 $O(n)$ 的算法。

首先，顯然 $1^{-1} \equiv 1\pmod p$。

其餘我們遞迴求解，假設現在要求 $i^{-1}$，令 $k = \lfloor \frac{p}{i} \rfloor$, $j = p\bmod i$，有 $p = ik + j$。
放到$\bmod p$ 下會得到 $ik + j \equiv 0\pmod p$，兩邊同乘 $i^{-1}\times j^{-1}$：

$j^{-1}k + i^{-1} \equiv 0\pmod p$
$i^{-1} \equiv -kj^{-1}\pmod p$
$i^{-1} \equiv -k\times {(p\bmod i)}^{-1}\pmod p$
$i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \times {(p\bmod i)}^{-1}\pmod p$

觀察到 $p \bmod i < i$，遞迴時完全可以假設我們算 $i$ 時已經知道所有 $j < i$ 的模逆元 $j^{-1}$，也就是說我們推出了模逆元的遞迴式，以迭代實作。

$$i^{-1} = \begin{cases}
1&:n=1\\
-\lfloor \frac{p}{i} \rfloor \times {(p\bmod i)}^{-1}&:\text{Otherwise}
\end{cases}$$

inv[1] = 1;
for(int i=2;i<=n;i++)
{
    inv[i] = (long long)(p - p/i) * inv[p%i] % p;
}

用 $p - \lfloor \frac{p}{i} \rfloor$ 防止出現負數。

注意到 inv[0] 是未定義的，若遇到 $i\mid p$ 的情況，程式會使用到 inv[0]，因為 $i\mid p$ 時 $i^{-1}$ 不存在。

(此章節參考自[OI-wiki 乘法逆元](https://oi-wiki.org/math/number-theory/inverse/#线性求逆元))

## 模逆元應用

可快速算出$C_m^n$

$C_m^n=\frac {n!}{m!\times (n-m)!}$

$C_m^n=pre[n]\times pre_i[m]\times pre_i[n-m]$

:::spoiler code

#include<bits/stdc++.h>
#define Crbubble cin.tie(0); ios_base::sync_with_stdio(false);
#define ll long long

using namespace std;

const ll MAXN = 100005;
const ll mod = 998244353;
ll pre[MAXN];
ll pre_i[MAXN];
ll inv[MAXN];

ll f_pow(ll a, ll b)
{
	ll base = a, cou = 1;
	while(b)
	{
		if(b & 1) cou *= base;
		base *= base;
		cou %= mod;
		base %= mod;
		b /= 2;
	}
	return cou;
}

ll f_inv(ll n)
{
	 return f_pow(n,mod-2);
}

void build(ll n)
{
	pre[0] = pre[1] = 1;
	pre_i[0] = pre_i[1] = 1;
	inv[0] = inv[1] = 1;
	for(int i=2;i<=n;i++)
	{
		pre[i] = pre[i-1] * i % mod;
		inv[i] = f_inv(i);
		pre_i[i] = pre_i[i-1] * inv[i] % mod;
	}
}

ll C(ll n, ll m)
{
	return pre[n] * pre_i[m] % mod * pre_i[n-m] % mod;
}

int main()
{	Crbubble
	build(MAXN);
	cout << inv[4] << endl;
	cout << C(6,3) << endl;
	return 0;
}

:::

## 例題(?)

- [Codeforces 1546D](https://codeforces.com/contest/1546/problem/D) D - AquaMoon and Chess
:::spoiler 想法
可以觀察到兩個1可以配成一組，我們只需算出共有$m$組1，然後把1插入0(設有$n$個0)之間，$C_{m}^{n+m}$即為答案
:::