数论、组合数学、线性代数学习笔记
medal_dreams
·
2026-05-13 07:52:32
·
算法·理论
:::warning{open}
本文使用 deepseek 进行了一定的语言润色和语言错误查找，以及一部分的证明任务，以保证本文的语言是尽量准确的，但保证人类贡献严格大于 AI。
不然我复习什么。
:::
本文章对于形式相同的我放在一块了，但并不代表读者可以完全按照我这个顺序学习，如果你是复习当我没说，在明显需要前置知识的地方我会标注，此时推荐读者先学习完前置知识后学习这个知识。
数论
常见符号
当然如果你不知道第二个符号可以继续向下看，我后面会说互质是什么。
特殊约定：
以下 [[x,y]] 表示闭区间 [x,y] 中的所有整数构成的集合。((x,y)) 表示开区间 (x,y) 中所有整数构成的集合。
质数（素数）
定义一个整数 p(p > 1) 是质数，当且仅当只有 1|p \land p|p ，即 p 没有除了 1,p 以外的任何正整数因数。\
特别地，1 不是质数。
判断方法
1. 试除法
我们发现，对于一个数 p ，其可以表示成两个数相乘，则其较小的因数最大不超过 \sqrt p 。考虑枚举 [[2,\sqrt p]] 所有数，判断其是否是 p 的因数，即是否有 p \equiv 0 \pmod i ，若是，则 p 不是质数。
时间复杂度 O(\sqrt p) 。
优点：
简单，暴力，在对于小数或较稀疏的数较优。
缺点：
对于枚举 [[1,n]] 中所有质数的时候复杂度不优，为 O(n \sqrt n) 。
:::info[实现]
bool check(int x)
{
for(int i = 2;i <= sqrt(x);i ++) if(x % i == 0) return false;
return true;
}:::
例题
P1304 哥德巴赫猜想
2. 埃氏筛
其用于替代求 [[1,n]] 质数不优的试除法。
发现若一个数 p 是质数，则 2\times p,3 \times p,\cdots,\left \lfloor \frac{n}{p} \right \rfloor \times p 都不是质数，我们考虑标记这些数，在判断下一个数的时候判断其是否被标记，没有既是质数。
时间复杂度 O(n \log\log n) 可以使用 bitset 优化，在一些时候会比欧拉筛快。
直接给 bitset 代码了。
:::info[bitset]
bitset<N> b;
void eltsn(int n)//n 是上界
{
b.set(1), b.set(0);
for(int i = 2;i <= n;i ++) if(!b.test(i)) for(int j = i * 2;j <= n;j += i) b.set(j);
}:::
优点
可以使用 bitset 优化；速度比试除法快。
缺点
没有欧拉筛全能，没有办法求欧拉函数。
3. 欧拉筛
考虑到埃氏筛时间复杂度瓶颈在于多次标记一个数，我们考虑让一个数只被其最小质因数标记，这样每个数只会被标记一次。
实现就是用一个数组记录所有质数，每次拿出来标记就可以了。
时间复杂度 O(n) 。
:::info[代码]
vector<int> pr;
bitset<N> ispr;
void Ol(int n)
{
ispr.set(1), ispr.set(0);
for(int i = 2;i <= n;i ++)
{
if(!ispr.test(i)) pr.push_back(i);
for(auto p : pr)
{
if(p * i > n) break;
ispr.set(p * i);
if(i % p == 0) break;
}
}
}:::
优点
时间复杂度最低，可以求欧拉函数，同时可以处理出每个质数。
缺点
筛法只能求 [[1,n]] 的数，对于稀疏的数不优。并且欧拉筛没有埃氏筛优化那么快。
例题
P1217 [USACO1.5] 回文质数 Prime Palindromes\
P3383 【模板】线性筛素数\
P3912 素数个数\
P5736 【深基7.例2】质数筛\
P5723 【深基4.例13】质数口袋
4.质因数分解
枚举每一个质数，直至除尽即可，我一般用欧拉筛。
:::info[欧拉筛求质因数代码]
Ol(n);
for(auto p : pr) while(n % p == 0) ans.push_back(p), n /= p;
for(auto p : ans) cout << p << ' ';:::
:::info[试除法求质因数分解代码]
vector<int> prime_resolve(int x)
{
vector<int> ans;
for(int i = 2;i <= sqrt(x) && x > 1;i ++)
{
if(x % i) continue;
ans.push_back(i);
while(x % i == 0) x /= i;
}
if(x > 1) ans.push_back(x);
return ans;
}:::
例题
P1075 [NOIP 2012 普及组] 质因数分解\
B3715 分解质因子 2 \
B3716 分解质因子 3
因数
唯一分解定理
任何一个数 m \in [[2,+ \infty)) ，都可以唯一分解为 m = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n} 。
其中 p_1,p_2,\cdots,p_n 为质数。
可见，一个数的因数个数为
(a_1 + 1) \times (a_2 + 1) \times \cdots \times (a_n + 1)
因数之和为
(p_1^0+p_1^1+\cdots+p_1^{a_1}) \times (p_2^0+p_2^1+\cdots+p_2^{a_2}) \times \cdots \times (p_n^0+p_n^1+\cdots+p_n^{a_n})
可得因数之和为 \prod_{i=1}^{n} \frac{p_i^{a_i + 1} -1}{p_i - 1} 。
最大公因数
公因数，即两个数公共的因数。
所以对于两个数 x,y ，d 为其公因数当且仅当 d|x \land d|y 。
最大公因数即 \displaystyle \max_d d|x \land d|y ，记 \gcd(x,y) 为 x,y 的最大公约数。
当 d = 1 时，我们称 x,y 互质。
辗转相除法
一般我们使用辗转相除法求 \gcd ，即有 \gcd(x,y) = \gcd(y,x \bmod y) ，当 y = 0 时，最大公约数为 x 。
:::info[简单证明]
设 x = yk+c ，显然有 c = x \bmod y ，设 d 为 x,y 的公约数，则有 c = x-yk 则 \frac{c}{d} = \frac{x}{d} - \frac{y}{d}k 。可见 d|c ，故若 d 是 x,y 的公约数，则 d 也是 y,x \bmod y 的公约数。
反过来亦然。
:::
:::info[代码]
int gcd(int x, int y){return y == 0 ? x : gcd(y, x % y);}:::
更相减损法
古人的智慧。
\gcd(x,y) = \gcd(y,x-y) = \gcd(x,x-y)
:::info[证明]
若 $d
x \land d
y 则明显 d
(x-y)$。
其用途不大，因为时间不如辗转相除法，但是在高精度领域比较吃香，因为高精度取模是不好取的，而减法相对于取模是好写的。
最小公倍数
公倍数，即两个数公共的倍数。
故 d 是 x,y 的公倍数当且仅当 x|d \land y|d 。
最小公倍数就是 \displaystyle \min_d x|d \land y|d ，记其为 \operatorname{lcm}(x,y) 。
其中计算可以转换为 \operatorname{lcm}(x,y) = \frac{x \times y}{\gcd(x,y)} 。
例题
P8469 [Aya Round 1 D] 文文的数学游戏
快速幂
对于 a^b 的这个数，我们若想快速计算，就要用到倍增知识，发现对于 b 的二进制位 i ，都对应 x^{2i} 即若有 x^i 我们可以用 x^i \times x^i 得出这个数，当 i 位上的数是 1 ，我们就可以记录答案。
:::info[代码]
using ll = long long;
ll qpow(ll x, ll y, ll mod)
{
ll res = 1;
while(y)
{
if(y & 1) res *= x, res %= mod;
x = x * x;x %= mod;y >>= 1;
}
return res;
}:::
模板题
P1226 【模板】快速幂
欧拉函数
定义 y \in [[1,x-1]],\varphi(x) = \sum [\gcd(x,y) = 1] 。
通俗来讲，\varphi(x) 就是 1 \sim x-1 中与 x 互质的整数。
特别地，\varphi(1) = 1 。
求法
公式解
将 x 唯一分解，则有 \varphi(x) = x \times \prod_i^k (1 - \frac{1}{p_i}) 。
或者我们还有一种写法，即 \varphi(x) = \prod_i^k ((p_i - 1) \times p_i^{a_i-1}) 。
::::info[代码]
:::info[写法 1]
a = n;
Ol(n);
for(auto p : pr)
{
if(n % p == 0) ans.push_back(p);
while(n % p == 0) n /= p;
}
for(auto p : ans) a = (a * (p - 1) / p);:::
:::info[写法 2]
int phi(int x)
{
int ans = 1;
for(int i = 2;i <= sqrtl(x);i ++)
{
if(x % i == 0) ans *= (i - 1), x /= i;
while(x % i == 0) ans *= i, x /= i;
}
if(x > 1) ans *= (x - 1);
return ans;
}:::
::::
欧拉筛解
通常用于求解 i \in [[1,n]] 中 \varphi(i) 。
性质
首先定义积性函数：\
定义一个函数 f(x) 是积性函数，当且仅当若 \gcd(x,y)=1 ，则 f(xy) = f(x)\times f(y) 。
故欧拉函数有以下性质：
欧拉函数是积性函数。
设 p 为质数，若 p | n 且 p^2 | n ，则 \varphi(n) = \varphi(\frac{n}{p}) \times p 。
设 p 为质数，若 p|n 且 p^2 \nmid n ，则 \varphi(n) = \varphi(\frac{n}{p}) \times (p-1) 。
:::info[证明]
显然吧，对于 \gcd(x,y) = 1 的，明显 x,y 没有相同因数，故唯一分解没有任何相同质因数，可以直接套用欧拉函数公式得证。
说明 n 和 \frac{n}{p} 有相同的质因子，而其只关注质因子，故有：
\varphi(n) = n \times (1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})
\\
\varphi(\frac{n}{p}) = \frac{n}{p} \times (1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})
可见，其商为 p 。
可得 \gcd(n,\frac{n}{p}) = 1 而 \varphi(n) = \varphi(\frac{n}{p})\varphi(p) ，而 \varphi(p) = p - 1 ，得证。
:::
所以我们可以将其和欧拉筛联系起来。
:::info[代码]
int phi[N];
vector<int> pr, ans;
bitset<N> ispr;
void Ol(int n)
{
ispr.set(1), ispr.set(0);phi[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(!ispr.test(i)) pr.push_back(i), phi[i] = i - 1;
for(auto p : pr)
{
if(p * i > n) break;
ispr.set(p * i);phi[p * i] = phi[i] * (p - 1);//先默认为性质一
if(i % p == 0) {phi[p * i] = phi[i] * p;break;}//最小质因数对应的 p*i 肯定有 p^2|i 则为性质二
}
}
}:::
同余
定义 x 除以 p 的余数和 y 除以 p 的余数相等，符号表示为 x \equiv y \pmod p 。
其满足以下性质：
其实还是挺简单的，不证明了。
同余系和剩余系
其实我觉得没什么用。
同余类/剩余类 ：所有模 n 同余 的整数组成的集合叫做同余类或说剩余类 。
完全剩余系 ：从模 n 的每个剩余类中各取 一个数，得到的 n 个数的集合叫做模 n 的完全剩余系 ，简称完系 。
最小非负完全剩余系 ：即集合 A = \{x|x \in N \land x < n\} 。
简化剩余系 ：也称既约剩余系或缩系 ，在与 n 互质 的全体 剩余类中各选择一个数组成的集合。\
### 欧拉定理
若 $\gcd(a,n) = 1$，则 $a^{\varphi(n)} \equiv 1 \pmod n$。
:::info[证明]
设集合 $A$ 为 $n$ 的一个缩系，且 $\forall i \in A,1 \le i < n$。因为 $\gcd(a,n) = 1$，有 $B = \{i\times a|i \in A\}$。
所以有
$$
(ai_1)(ai_2)\cdots(ai_{\varphi(n)}) \equiv (i_1)(i_2)\cdots(i_{\varphi(n)}) \pmod n
$$
即
$$
a^{\varphi(n)}(i_1)(i_2)\cdots(i_{\varphi(n)}) \equiv (i_1)(i_2)\cdots(i_{\varphi(n)}) \pmod n
$$
那就有
$$
a^{\varphi(n)} \equiv 1 \pmod n
$$
:::
### 费马小定理
若 $\gcd(a,p)=1$ 且 $p$ 为素数，则 $a^{p-1} \equiv 1 \pmod p$。
:::info[证明]
欧拉定理的特殊情况。\
可见 $\varphi(p) = p - 1$。
:::
### 扩展欧拉定理
这个知识涉及到较高深的思想，推荐先学习完初等数论（至少是 CRT 后）再学习此知识。
对于 $a^b \bmod m$ 有
$$
a^b \equiv a^{b \bmod \varphi(m)} \pmod m \qquad \gcd(a,m) = 1
\\
a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m \qquad b \ge \varphi(m)
$$
其中第一行为第二行的特殊形式。
:::info[证明]
~~我不会。~~
用 deepseek 证明的。
本证明涉及中国剩余定理，推荐先学习下面内容后看。
将 $m$ 分解为素数幂的乘积 $m = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$。由中国剩余定理，只需证明对每个素数幂 $p^e \mid m$ 有
$$ a^b \equiv a^{\varphi(m)+r} \pmod{p^e}. $$
固定 $p^e$，分两种情况。
**情形1：$p \nmid a$**
此时 $\gcd(a, p^e)=1$。由欧拉定理，$a^{\varphi(p^e)} \equiv 1 \pmod{p^e}$。因为 $\varphi(p^e) \mid \varphi(m)$，所以 $a^{\varphi(m)} \equiv 1 \pmod{p^e}$。
设 $b = q\varphi(m) + r$（$q \ge 1$），则
$$ a^b = a^{q\varphi(m)+r} = (a^{\varphi(m)})^q a^r \equiv a^r \pmod{p^e}, $$
而 $a^{\varphi(m)+r} = a^{\varphi(m)} a^r \equiv a^r \pmod{p^e}$，故成立。
**情形2：$p \mid a$**
设 $a = p^d a'$，其中 $d \ge 1$，$p \nmid a'$。则
$$ a^b = p^{db}(a')^b,\quad a^{\varphi(m)+r} = p^{d(\varphi(m)+r)}(a')^{\varphi(m)+r}. $$
由于 $b \ge \varphi(m) \ge \varphi(p^e) = p^{e-1}(p-1)$，且易证 $\varphi(p^e) \ge e$，故 $b \ge e$。于是 $db \ge d\cdot e \ge e$，所以 $p^e \mid p^{db}$，即 $a^b \equiv 0 \pmod{p^e}$。
同理，$\varphi(m)+r \ge \varphi(m) \ge \varphi(p^e) \ge e$，得 $d(\varphi(m)+r) \ge e$，故 $a^{\varphi(m)+r} \equiv 0 \pmod{p^e}$。两边均为 $0$，成立。
综上，对每个 $p^e \mid m$ 同余式成立，由中国剩余定理得证。
:::
[P5091 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)。
### 裴蜀定理
对于任意整数 $a,b$，设 $d=\gcd(a,b)$，则对于所有整数 $x,y$ 都有 $d|(ax+by)$。特别地，一定存在一对 $x,y$，满足 $ax+by=d$。
:::info[证明]
裴蜀定理证明涉及到 exgcd 的思想，学习完裴蜀定理后学习 exgcd 会简单一点。
对于第一点，明显成立。
对于第二点：
1. 对于 $b = 0$ 时，$x=1,y=0$ 原式成立。
2. 否则我们可以思考求 $\gcd$ 的过程，假设存在 $x,y$ 使 $bx + (a \bmod b)y = \gcd(b, a\bmod b)$，则有 $bx + (a-b\left\lfloor \frac{a}{b}\right\rfloor)y = ay + b(x - \left\lfloor \frac{a}{b}\right\rfloor y)$，我们可以令 $x' = y,y' = x - \left\lfloor \frac{a}{b}\right\rfloor y$，就有 $ax'+by' = \gcd(a,b)$。
那就是递归求解到 $b=0$ 时，我们就有 $x,y$ 的具体解，并且根据上述，$x,y$ 是一定有解的。
:::
[P4549 【模板】裴蜀定理](https://www.luogu.com.cn/problem/P4549)。
### exgcd
其用于求解 $ax+by = c$ 的不定方程的一组特解。
根据裴蜀定理，我们可以求出 $ax+by = \gcd(a,b)$。\
那若 $\gcd(a,b)|c$ 则我们可以求出 $ax+by = \gcd(a,b)$ 的一组解 $x,y$ 后面使其变成 $x \times \frac{c}{\gcd(a,b)}, y \times \frac{c}{\gcd(a,b)}$ 即可。\
若 $\gcd(a,b)\nmid c$，则无解。
其也可用于求解裴蜀定理的解。
:::info[代码]
```cpp
int exgcd(int &x, int &y, int a, int b)
{
if(b == 0) {x = 1, y = 0;return a;}
int d = exgcd(y, x, b, a % b);
y -= (a / b) * x;
return d;
}
```
:::
#### 例题
[P5656 【模板】二元一次不定方程 (exgcd)](https://www.luogu.com.cn/problem/P5656)
[P2421 [NOI2002] 荒岛野人](https://www.luogu.com.cn/problem/P2421)
#### 变形
求解线性同余方程。
线性同余方程是形如 $ax \equiv b \pmod p$ 的式子，也称为一次同余方程。
可以将其转化为 $ax + py \equiv b \pmod p$。
故此方程有解当且仅当 $\gcd(a,p) | b$，求解 $x,y$ 后只用 $x$ 即可。
##### 模板
[P1082 [NOIP 2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)。
### 逆元
我们知道 $x \times \frac{1}{x} = 1(x \neq 0)$，其中 $x$ 的在实数范围内逆元就是 $\frac{1}{x}$，而我们通常需要用的是模意义下的逆元，也就是在模意义下和 $\frac{1}{x}$ 功能相同的数。
形式的说，若 $y$ 是 $x$ 在模 $p$ 意义下的逆元，则有 $xy \equiv 1 \pmod p$。
#### 求法
这里介绍四种求法。
##### 费马小定理求解
若满足 $p$ 是质数，且 $\gcd(x,p) = 1$，我们由费马小定理得 $x^{p-1} \equiv 1 \pmod p$，那么若有 $x^{p-2}$，其就相当于“除以”了一个 $x$，则 $x^{p-2} \equiv x^{-1} \pmod p$ 这个 $x^{-1}$ 就是 $x$ 在模 $p$ 意义下的逆元。快速幂求解即可。
其缺点就是必须满足 $p$ 是质数，且 $\gcd(x,p) = 1$。时间复杂度是 $O(\log p)$，还是很优的。
代码过于简单，不展示了。
##### exgcd求逆元
看两眼 $xy \equiv 1 \pmod p$，这不就是线性同余方程吗，解方程即可，注意这个要满足 $\gcd(x,p) = 1$。
注意 $y$ 可能会为负数，我们让其变为 $(y+p) \bmod p$ 即可。
这个代码和上面的给出的 exgcd 代码相似。
##### 线性求逆元
根据逆元存在定理，exgcd 求是一定满足的，但是时间复杂度可能在求 $1 \sim n$ 的逆元并不优秀，我们可以使用线性求逆元。
> 逆元存在定理：$x$ 在模 $p$ 意义下存在逆元当且仅当 $\gcd(x,p) = 1$。
但是这个预处理的时间复杂度是严格 $O(n)$ 的。
其公式为 $inv_i \equiv - \left\lfloor \frac{p}{i} \right\rfloor \times inv_{p \bmod i} \pmod p$。\
其中我们认为 $inv_1 = 1
:::info[证明]
令 p = ki + r ，则 ki + r \equiv 0 \pmod p \Leftrightarrow r \equiv -ki \pmod p 。
同乘 i^{-1},r^{-1} ，则有 rr^{-1}i^{-1} \equiv -kii^{-1}r^{-1} \pmod p \Leftrightarrow i^{-1} \equiv -kr^{-1} \pmod p 。
其中 k = \left\lfloor \frac{p}{i} \right\rfloor ，则有 i^{-1} \equiv -\left\lfloor \frac{p}{i} \right\rfloor r^{-1} \pmod p \Leftrightarrow i^{-1} \equiv -\left\lfloor \frac{p}{i} \right\rfloor (p \bmod i)^{-1} \pmod p 。
:::
这样我们就可以线性求逆了。
:::info[代码]
inv[1] = 1;
for(int i = 2;i <= n;i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;:::
特殊数列求逆
阶乘线性求逆。
求出 (n!)^{-1} 一般可以使用费马小定理求逆元，求 (i!)^{-1} 依次相乘对应的 i+1 即可。
即 (x!)^{-1} \equiv [(x+1)!]^{-1} \times (x+1) 。
:::info[代码]
把 3e6 改成你需要的数即可。
pw[0] = 1;ipw[0] = 1;
for(int i = 1;i <= 3e6;i ++) pw[i] = pw[i - 1] * i % mod;
ipw[3000000] = qpow(pw[3000000], mod - 2);
for(int i = 3e6 - 1;i >= 1;i --) ipw[i] = ipw[i + 1] * (i + 1) % mod;:::
模板题
P3811 【模板】模意义下的乘法逆元
CRT（中国剩余定理）
其用于求解多个线性同余方程组。
即：给定 n 个线性同余方程：
\begin{cases}
x \equiv a_1 \pmod {m_1}
\\
x \equiv a_2 \pmod {m_2}
\\
\cdots
\\
x \equiv a_n \pmod {m_n}
\end{cases}
保证 m_1,m_2,\cdots,m_n 两两互质，求 x 的通解。
答案
设 M = \prod_{i=1}^n m_i，M_i = M \div m_i,t_iM_i \equiv 1 \pmod {m_i} 。
则有 x \equiv \sum_{i = 1} ^ n a_it_iM_i \pmod M 。
::::info[证明]
以下所有变量都和上文有关。
考虑解 n 个方程组，其中第 i 个方程组只对 a_i 有影响。
即我们构造这样的方程组：
\begin{cases}
x \equiv 0 \pmod {m_1}
\\
x \equiv 0 \pmod {m_2}
\\
\cdots
\\
x \equiv 1 \pmod {m_i}
\\
\cdots
\\
x \equiv 0 \pmod {m_n}
\end{cases}
合并可得
\begin{cases}
x \equiv 0 \pmod {\frac{M}{m_i}}
\\
x \equiv 1 \pmod {m_i}
\end{cases}
\Leftrightarrow
\begin{cases}
x \equiv 0 \pmod {M_i}
\\
x \equiv 1 \pmod {m_i}
\end{cases}
\Leftrightarrow
t_iM_i \equiv 1 \pmod {m_i}
因为 m_i 两两互质，我们考虑求解 t_i 。根据逆元存在性定理，t_i 一定存在。
最后的解 x 就是每个方程组都成立的解，即 x \equiv \sum_{i=1}^n a_ix_i \equiv \sum_{i=1}^n a_iM_it_i \pmod M 。
:::info[为什么可以得出来 x \equiv \sum_{i=1}^n a_ix_i \pmod M ？]
因为每个解 x_i \times a_i 都满足对于 m_i 其与 a_i 同余，同时满足 x_i 对其他 m_j,j \neq i 都与 0 同余。
故所有解都满足条件，合并起来就满足了所有同余方程。
而模 M 是因为 m_1,m_2,\cdots,m_n 两两互质，若我们构造出一个特解 x ，则所有其他解都可以通过 x \times qM 这个操作得到（q \in N_+ ），所以我们只需要模 M 这个特解即可。
:::
::::
P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
:::warning[注意]
一般在求 CRT 的过程中是会爆 long long 的，注意开 __int128。
:::
:::info[代码]
read(n);
int M = 1,ans = 0;
for(int i = 1;i <= n;i ++) read(p[i]),read(m[i]),M *= p[i];
for(int i = 1;i <= n;i ++)
{
int mm = M / p[i];
int x,y;
exgcd(p[i],mm,x,y);//求逆元
ans = (ans + m[i] * mm * y) % M;
}
print((ans % M + M) % M);//防止为负数:::
exCRT（扩展中国剩余定理）
取消了 m_1,m_2,\cdots,m_n 互质的条件。
CRT 的思路很明显是没有前途的，在面对不互质的条件根本没法做。
考虑新想法。我们发现 CRT 中我们最后用了合并的做法，所以我们思考能不能用合并 解决这道题。
我们考虑只有两个方程组：
\begin{cases}
x \equiv a_1 \pmod {m_1}
\\
x \equiv a_2 \pmod {m_2}
\end{cases}
考虑先化成 x = a_1+m_1m = a_2+m_2n 的形式。
可得 m_1m-m_2n = a_2-a_1 。
因为我们想求最小的 x \in N_+ ，所以 m,n 就要尽可能小。\
考虑我们用 exgcd 求出一组特解 m,n ，则通解 m'=m-\frac{m_2}{d}k, n' = n + \frac{m_1}{d}k ，其中 d = \gcd(m_1,m_2) 。
:::info[为什么通解是这个]
因为我们 exgcd 求出的是 m_1m+m_2n=d 的一组特解，若有一组通解 m',n' 使得 m_1m'+m_2n'=d ，令两式相减，得 m_1(m'-m)+m_2(n'-n)=0 这是个其次方程。
而我们可以得出齐次方程 m_1 \Delta m + m_2 \Delta n = 0 通解为 \Delta m = -\frac{m_2}{d}k, \Delta n = \frac{m_1}{d}k 。
故通解 m',n' 可以用 m'=m-\frac{m_2}{d}k, n' = n + \frac{m_1}{d}k 表示。
:::
因为我们只需要一个 m' 或 n' ，所以我们只需要让一个尽可能小。\
考虑使 m' 最小，故有 m_0 = m \bmod \frac{m_2}{d} 。\
则有 x \equiv m_1 \frac{a_2-a_1}{d}m_0+a_1 \pmod {\operatorname{lcm}(m_1,m_2)} 。\
其中 \frac{a_2-a_1}{d} 是我们求 exgcd 对于最终答案要增大的倍数，不会推荐重学 exgcd，其他的就是上面构造 x 的式子。
我们也可以看出若无解就是有 d \nmid a_2-a_1 因为我们要保证不定方程有解。
之后就对于每个式子依次合并即可，最后答案就是最后一个式子的 a_n 。
:::info[代码]
read(n);
for(int i = 1;i <= n;i ++) read(a[i].second), read(a[i].first);
for(int i = 2;i <= n;i ++)
{
int s = a[i - 1].first, ss = a[i].first, a1 = a[i - 1].second, a2 = a[i].second, x, y;
int B = ss - s, d = exgcd(x, y, a1, a2);
if(B % d) {cout << -1;return 0;}//无解
a2 /= d;//先除以了吧
a[i].first = B / d % a2 * x % a2;//求 m0
while(a[i].first < 0) a[i].first += a2;//防止为负
a[i].first = a1 * a[i].first + s;//求合并的 a
a[i].second = a1 * a2;//求合并的 m
}
put(a[n].first);:::
P4777 【模板】扩展中国剩余定理（EXCRT）
二次剩余
其用来求解 x^2 \equiv n \pmod p ，其中 p,n 给定，p 是奇素数。
定义
对于正整数 n ，奇素数 p \nmid n ，若存在正整数 x 使得 x^2 \equiv n \pmod p ，则 n 为模 p 的二次剩余。
我们首先定义勒让德符号：
(\frac{n}{p}) =
\begin{cases}
1 & n 是 p 的二次剩余
\\
-1 & n 不是 p 的二次剩余
\\
0 & p | n
\end{cases}
那则有以下两条定理。
定理
(\frac{n}{p}) \equiv n^{\frac{p-1}{2}} \pmod p
:::info[证明]
定理一证明 ：
我们首先要知道一个定理：
威尔逊定理：对于一个质数 p ，有 (p-1)! \equiv -1 \pmod p 。
我们分情况讨论：\
若 (\frac{n}{p}) = 1 则 n^{\frac{p-1}{2}} = (\sqrt n) ^ {p-1} \equiv 1 \pmod p （若 n \nmid p 则 \sqrt n \nmid p ）。\
若 (\frac{n}{p}) = 0 ，则 n \equiv 0 \pmod p ，则 n^{\frac{p-1}{2}} \equiv 0 \pmod p 。\
若 (\frac{n}{p}) = -1 ，则根据 exgcd，对 i \in [[1, p-1]] 都有唯一 j \in [[1, p-1]],i \neq j 满足 ij \equiv n \pmod p 。这样的数对有 \frac{p-1}{2} 个，因此将这些相乘有 n^{\frac{p-1}{2}} \equiv (p-1)! \pmod p 。由威尔逊定理，有 (p-1)! \equiv -1 \pmod p \Rightarrow n^{\frac{p-1}{2}} \equiv -1 \pmod p 。
定理二证明 ：
设有 x,y \in [[1, p-1]],x \neq y 有 x^2 \equiv y^2 \pmod p ，则有 (x+y)(x-y) \equiv 0 \pmod p 。
由于 $0 <
x - y
< p 必有 x+y \equiv 0 \pmod p，这样的数对共 \frac{p-1}{2}，因此共有 \frac{p-1}{2}$ 个二次剩余。
求解方法
考虑在 [0,p-1] 中随机产生一个数 a ，令 w = a^2-n ，若 (\frac{w}{p}) = -1 ，则 (a+\sqrt w)^{\frac{p-1}{2}} 就是 x 的一个解。
:::info[证明]
对于 x \in [1,p-1] 显然 C_p^x \equiv 0 \pmod p 。因此 (a + \sqrt w) ^ p = \sum_{i=0}^p C_p^i a^i(\sqrt w)^{p-i} \equiv a^p+(\sqrt w)^p ，根据费马小定理，有 a_p \equiv a \pmod p 。根据定理一 (\sqrt w)^p = \sqrt w w ^ {\frac{p - 1}{2}} \equiv - \sqrt w ，因此 (a+\sqrt w) ^ {p+1} \equiv (a + \sqrt w)(a - \sqrt w) = a^2 - w = n 。
开根即可。
:::
有一个问题是 w 并不是二次剩余，我们又怎么求 \sqrt w ，这样不就“没”了吗？
我们可以考虑扩域思想，定义 \mathbb{Z}_p[\sqrt w] = \{a+b \sqrt w|a, b \in Z \cap [0,p)\} 。
我们可知在模 p 意义下这个扩域上的乘法是可以定义的，即 (a_1+b_1 \sqrt w)(a_2+b_2 \sqrt w) \bmod p = (a_1a_2+b_1b_2w) \bmod p + ((a_1b_2+b_1a_2) \bmod p) \sqrt w ，这样我们就可以实现快速幂了。
时间复杂度
由于 [1, p-1] 有一半是二次剩余，故我们随机的期望次数为 2 ，这样我们就可以求出一个二次剩余解，另一个解为其相反数。
:::info[代码]
ll lrd(ll x, ll mod){return qpow(x, mod >> 1);}//定理一
struct Z{
ll x, y;
Z operator * (Z s){return {(x * s.x % mod + y * s.y % mod * w % mod) % mod, (x * s.y % mod + y * s.x % mod) % mod};}
};//扩域
Z qpow(Z x, ll y)
{
Z c = {1, 0};
while(y)
{
if(y & 1) c = c * x;
x = x * x;y >>= 1;
}
return c;
}
void Ciallo(int n, int mod)
{
n %= mod;ll x = lrd(n, mod);
if(x == mod - 1) cout << "Hola!\n";
else if(x == 0) cout << 0 << '\n';
else
{
x = rd() % (mod - 1) + 1;w = (1ll * x * x - n + mod) % mod;
while(lrd(w, mod) <= 1) x = rd() % (mod - 1) + 1, w = (1ll * x * x - n + mod) % mod;// w 要无解 而我的勒让德只能决定 0 和 1，则其他的都是 -1
Z a = {x, 1};a = qpow(a, mod + 1 >> 1);
ll ans1 = a.x, ans2 = mod - a.x;
cout << min(ans1, ans2) << ' ' << max(ans1, ans2) << '\n';
}
return
}:::
P5491 【模板】二次剩余
BSGS（大步小步算法）
其实我一直记成 BGSG。
其用于求解形如 a^x \equiv b \pmod p 的方程的最小整数解，其中 a,b,p 给定。对于 BSGS，我们保证 \gcd(a,p) = 1 ，求出来的 x 称为 a \bmod p 意义下的离散对数。
根据欧拉定理有 a^x \equiv a^{x \bmod \varphi(p)} \pmod p 。所以 a 的幂次在模 p 意义下有长度为 \varphi(p) 的循环节。
所以我们可以直接暴力枚举 [[1,\varphi(p)]] 中的数 i ，对于每个 a^i 判断其是否满足 a^i \equiv b \pmod p 。但 \varphi(p) 在 p 是质数时为 p-1 。所以算法最坏时间复杂度为 O(p) ，考虑优化。
考虑使用分块优化，令块长 c = \left\lceil \sqrt p \right\rceil ，我们可以将 x 写成 kc-B 的形式，其中 k \in [1,c],B \in [0,c-1] 则 \max x = c^2 \ge p > \varphi(p) 因此我们可以遍历到 \varphi(p) 的每一个数。 \
然后我们就有 a^{kc-B} \equiv b \pmod p ，乘上 a^B 有 a^{kc} \equiv b \times a^B \pmod p ，而右边一共有 c 个结果，我们存到哈希表中，枚举 k ，对每一个 a^{kc} 查询哈希表内是否存在这个值，如果存在，就返回答案 kc-B 。
:::info[代码]
map<ll, ll> mp;
ll BSGS(ll a, ll b, ll mod)
{
if(b == 1) return 0;
if(a % mod == b % mod) return 1;
if(a % mod == 0) return -1;
mp.clear();
ll c = ceil(sqrtl(mod));
for(ll i = 1, s = a;i <= c;i ++, s *= a, s %= mod) mp[b * s % mod] = i;
ll t = qpow(a, c, mod);
for(ll i = 1, s = t % mod;i <= c;i ++, s *= t, s %= mod) if(mp.count(s)) return c * i - mp[s];
return -1;
}:::
exBSGS
不保证 \gcd(a,p) = 1 。
考虑对方程两边和模数同时除以 d = \gcd(a,p) ，若 d = 1 就结束，否则就继续这个过程，令其执行次数为 k ，则我们有 \prod d = \gcd(a^k,p) ，可以发现若 \gcd(a^k,p) \nmid b 则方程无解。
:::info[证明&详细步骤]
每次消 \gcd 相当于从 a^x 中剥离出一个 a ，故最多只能剥离 x 次，所以 k \le x 。
设存在解 x ，则有 a^x - b \equiv 0 \pmod p ，即 p | (a^x-b) 。设 d = \gcd(a^k,p) ，因为 d|p ，则有 d|(a^x-b) ，同时由于 k \le x ，故有 a^x = a^k \times a^{x-k} ，因为 d|a^k ，所以 d|a^x ，故 d|b ，即
\begin{aligned}
a^x & \equiv b \pmod p
\\
\frac{a^k}{\gcd(a^k,p)} \times a^{x-k} & \equiv \frac{b}{\gcd(a^k,p)} \pmod {\frac{p}{\gcd(a^k,p)}}
\\
a^{x-k} & \equiv b \times (a^k)^{-1} \pmod {\frac{p}{\gcd(a^k,p)}}
\end{aligned}
因为 \gcd(a^k, \frac{p}{\gcd(a^k,p)}) = 1 ，故最后一步成立。
因为消 \gcd 次数满足 k\log p （每次至少有 p \leftarrow \left\lfloor \frac{p}{2} \right\rfloor ），枚举试除即可，时间复杂度 O(\sqrt p) 。
:::
:::info[代码]
ll BGSG(int mod, int b, int n, int pw)
{
mp.clear();
int c = ceil(sqrtl(mod));
for(int i = 1, aa = b;i <= c;i ++, aa = aa * b % mod) mp[n * aa % mod] = i;
ll t = qpow(b, c);
for(int i = 1, aa = pw * t % mod;i <= c;i ++, aa = aa * t % mod) if(mp.count(aa)) return c * i - mp[aa];
//aa这里我们要用pw开始，因为我们要满足 a^{x-k} * a^{k} 所以要有 a^k
return -1;
}
int gcd(int x, int y){return y == 0 ? x : gcd(y, x % y);}
ll exBGSG(int mod, int b, int n)
{
b %= mod, n %= mod;
if(n == 1 || mod == 1) return 0;
ll cnt = 0, pw = 1, d, ans;
while((d = gcd(b, mod)) != 1)
{
if(n % d) return -1;//无解
cnt ++;n /= d;mod /= d;//计算此时的次方数 和 需要同余的数 和模数
pw = (pw * b / d) % mod;//计算 a^k
if(pw == n) return cnt;//如果本来就够了就返回
}
ans = BGSG(mod, b, n, pw);//否则就进行BSGS
return ans == -1 ? -1 : ans + cnt;
}:::
原根与阶
定义
阶：对于 a\in Z,m \in N_+ ，若 \gcd(a,m) = 1 则 a^{\varphi(m)} \equiv 1 \pmod m 。我们定义满足 a^n \equiv 1 \pmod m 的最小正整数 n 称为 a 模 m 的阶，记作 \delta_m(a) 。
原根：设 m \in N_+, a\in Z ，若 \gcd(a,m) = 1 且 \delta_m(a) = \varphi(m) 则称 a 为模 m 的原根。
性质
性质太多我不想写证明了。
阶的三个性质
若 a^n \equiv 1 \pmod m 则 \delta_m(a) | n 。
设 m \in N_+ ，a,b \in Z \gcd(a,m) = \gcd(b,m) = 1 ，则 \delta_m(ab) = \delta_m(a)\delta_m(b) \Leftrightarrow \gcd(\delta_m(a), \delta_m(b)) = 1 。
设 k \in N, m \in N_+ , a\in Z, \gcd(a,m) = 1 ，则 \delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)} 。
原根的存在性定理
总共四条，明显我们知道 m = 1,2,4 时原根存在。
定理一：对于奇素数 p ，p 有原根。
定理二：对于奇素数 p ，a \in N_+ ，p^a 有原根。
定理三：对于奇素数 p ，a \in N_+ ，2p^a 的原根存在。
对于 m \not\in \{1,2,4\} 且不存在奇素数 p 及 a \in N_+ 使得 m\in\{p^a,2p^a\} ，则对任意 a \in Z,\gcd(a,m) = 1 都有 \delta_m(a) < \varphi(m) ，即模 m 的原根不存在 。
定理就这么多，想看证明的转步参考资料吧，太多了我属实不想写了。
求原根
所以我们知道 1,2,4 和奇素数 p^a 即 2p^a 有原根，其他数都没有原根。所以我们可以预处理素数，之后对其幂次进行标记，这个需要用素数筛。
然后我们判断这个数有没有原根，若一个数有原根我们就可以求出其最小正原根，根据王元的证明，我们可知若 m 有原根，其最小原根不多于 m^{0.25} 级别。
所以根据这个结论，我们可以从小到大枚举，由原根定义，若 g 为模 m 的原根，则对于 \varphi(m) 的任意质因数 p 必有 g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m ，故满足以上条件的一定是原根，我们可以分解 \varphi(m) 的所有质因数，用快速幂判断，若找到了一个最小原根 g ，则其他所有有 \gcd(x,\varphi(m)) = 1 的 x ，g^x 均为原根。
枚举即可。
可见我们还需要欧拉函数，故我们用欧拉筛并且做完后标记有无原根即可。
:::info[模板题代码]
using ll = long long;
#define int long long
constexpr int N = 2e6 + 66;
ll phi[N], Pr[N], tot;
bitset<N> isPr, pr;
void Ol(int n)
{
phi[1] = 1;isPr.set(1), isPr.set(0);
for(int i = 2;i <= n;i ++)
{
if(!isPr[i]) Pr[++ tot] = i, phi[i] = i - 1;
for(int j = 1;j <= tot;j ++)
{
if(i * Pr[j] > n) break;
phi[Pr[j] * i] = phi[i] * phi[Pr[j]];isPr.set(i * Pr[j]);
if(i % Pr[j] == 0) {phi[i * Pr[j]] = phi[i] * Pr[j];break;}
}
}
pr[1] = pr[2] = pr[4] = 1;
for(int i = 2;i <= tot;i ++) for(int j = Pr[i];j <= n;j *= Pr[i]) pr[j] = 1, pr[j * 2] = 1;
}//欧拉筛
vector<ll> G, ans;
ll t, n, d;
ll gcd(ll x, ll y){return y == 0 ? x : gcd(y, x % y);}//辗转相除法
ll qpow(ll x, ll y, ll mod)
{
ll res = 1;
while(y)
{
if(y & 1) res *= x, res %= mod;
x *= x;y >>= 1;x %= mod;
}
return res;
}//快速幂
bool check(int i, int n)
{
bool f = qpow(i, phi[n], n) == 1;//判断本身是否是原根
for(auto p : G)
if(qpow(i, phi[n] / p, n) % n == 1)//这些不能满足
f = 0;
return f;
//即满足 g^\phi(n) \equiv 1 \pmod n 但 \forall p \in prime \land p | \phi(n), g^{\phi(n)/p} \not\equiv 1 \pmod n
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
Ol(1e6);
cin >> t;
while(t --)
{
cin >> n >> d;
if(!pr[n]) {cout << "0\n\n";continue;}//如果没有原根
ans.clear();G.clear();
int p = phi[n], mn;
for(int j = 1;j <= tot;j ++)
{
if(p % Pr[j] == 0) G.push_back(Pr[j]);
while(p % Pr[j] == 0) p /= Pr[j];
}//拆质因数
for(int i = 1;i < n;i ++)
if(check(i, n))//若找到了最小原根
{mn = i;break;}
for(ll i = 1, j = mn;i <= phi[n];i ++, j *= mn, j %= n) if(gcd(i, phi[n]) == 1) ans.push_back(j);
//确定最小原根后若有 \gcd(i, \phi(n)) = 1 则 g^i 也是 n 的原根
sort(ans.begin(), ans.end());//从小到大排序
cout << ans.size() << '\n';
for(int i = 0;i < ans.size();i ++) if((i + 1) % d == 0) cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}:::
P6091 【模板】原根
P11961 [GESP202503 五级] 原根判断
莫比乌斯函数
定义
若 n = \prod_{i=1}^k p_i^{c_i} ，则有
\mu(n) =
\begin{cases}
1 & n = 1
\\
0 & \exists \, c_i \ge 2
\\
(-1)^k & otherwise
\end{cases}
性质
\begin{cases}
1 & n = 1
\\
0 & n\neq 1
\end{cases}
:::info[证明]
沿用上面对 n 的唯一分解，明显的 c_i \ge 2 对答案是没有贡献的，所以我们只用讨论 \prod_{i=1}^k p_i 部分，所以 $\sum_{d
n} \mu(d) = \sum{i=0}^k \dbinom{k}{i} (-1)^i = \sum {i=0}^k (1+(-1))^k，可见除了 n = 1，其余的都是 0$，这正证明了上式。
由 2 得 [gcd(i,j) = 1] = \sum_{d | gcd(i,j)} \mu(d) 。
求法
可以使用欧拉筛求，事实上，所有积性函数都可以使用欧拉筛求，无非就是快慢的事情。
莫比乌斯反演
对于一个函数 f(x) ，我们求其值，但只能较好求出其倍数和 或 因数和函数 g(x) ，则可以考虑莫比乌斯反演来快速求出 f(x) 的值。
对于其因数和函数，我们可设 f(n) = \sum_{d | n} g(d) ，莫比乌斯反演有 g(n) = \sum_{d | n} \mu(d) f(\frac{n}{d}) 。
::::info[证明]
给出两种证明方法。
:::info[狄利克雷卷积爆杀]
狄利克雷卷积：对于两个数论函数 f(x), g(x) ，他们狄利克雷卷积后的结果 h(x) 为 h(x) = \sum_{d|x} f(d)g(\frac{x}{d}) ，其可简化为 h = f * g 。
我们令 f,g 为数论函数，且满足 f(n) = \sum_{d | n} g(d) ，则我们可表示为 f = g * 1 。
同时与 \mu 卷积有 f * \mu = g * 1 * \mu = g * (1 * \mu) ，而 1 * \mu 就是上面的性质二，则有 $f * \mu = g \Leftrightarrow g(n) = \sum_{d
n} \mu(d) f(\frac{n}{d})$。
:::info[另一证明方法]
我们可知 \sum_{d|n} \mu(d) f(\frac{n}{d}) = \sum_{d | n} \mu(d) \sum_{d' | \frac{n}{d}} g(d') 。
这里需要理解一个常用技巧，交换求和顺序 。即交换求和符号达到简化运算的目的。当然这样有时候会导致一些值增加或者缺失，我们就要给其补上。本质就是要让里面的每一项的值的和等价 。
而 d,d' 都在 n 中，而且一个枚举另一个剩下的，则我们可以写成 $\sum_{d'
n} g(d') \sum_{d
\frac{n}{d'}} \mu(d) = \sum_{d'
n} g(d') [\frac{n}{d'} = 1] 而只有 d' = 1 才满足上式，则原式为 g(n)$。
::::
莫比乌斯反演还有另一种形式，令 f(n) = \sum_{n|d} g(d) ，则 g(n) = \sum_{n|d} \mu(\frac{d}{n}) f(d) ，其证明类似。
组合数学
排列组合
定义
\begin{aligned}
C_n^m &= \dbinom{n}{m} = \frac{n!}{m!(n-m)!}
\\
A^m_n &= \frac{n!}{(n-m)!}
\end{aligned}
其组合意义为：
C：在 n 个数里选 m 个，不考虑顺序。
A：在 n 个数里选 m 个，考虑顺序。
而 C 有递推公式 \dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1} 。
根据上面的定义，我们可以发现，\dbinom{n}{m} = \dbinom{n}{n-m} ，也就是说这两个是等价的，可以互相转化。
特别的，对于 m > n 或 m < 0 的时候在理论上我们认为其无意义，其值为 0 ，因为这样就可以扩展到一些定理。
二项式定理
组合数和杨辉三角有很深的关系。
二项式定理即：(a+b)^n = \sum_{i=0}^n \dbinom{n}{i} a^ib^{n-i} 。
:::info[证明]
我们将 (a+b)^n 展开，可以发现对于 a^ib^{n-i} ，其系数就是在 (a+b)(a+b)\cdots (a+b) 共 n 个 a+b 种选择 i 个 a+b 相乘得到的乘积的个数，也就是在 n 里面选 i 个的方案数，即 \dbinom{n}{i} 。
:::
若你画出来能发现 \dbinom{i}{j} 正好对应杨辉三角的第 i 行第 j 列，并且其递推式相同。
lucas（卢卡斯）定理
其用于 \dbinom{n}{m} \bmod p ，但 p 过于小的情况。
形式：
\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \times \dbinom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{m}{p} \right\rfloor} \pmod p
对于 \dbinom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{m}{p} \right\rfloor} 向下递归处理即可。
模板。
我不会证。 想看证明的可以移步 OIwiki。
:::info[代码]
ll C(int m, int n){return (n < m ? 0 : po[n] * impo[m] % p * impo[n - m] % p);}//po 为阶乘 impo 为阶乘逆元
ll lucas(int m, int n){return (m == n || m == 0 ? 1 : C(m % p, n % p) * lucas(m / p, n / p) % p);}:::
运算律
吸收率：\dbinom{n}{m} = \displaystyle \frac{n}{m} \dbinom{n-1}{m-1} ，其更一般的形式 \dbinom{n}{m}m^{\underline{i}} = \dbinom{n - i}{m - i}n^{\underline{i}} 。
例题 ：\
化简 \displaystyle \sum_{i=0}^n \dbinom{n}{i} \times i \times 2^i 。
:::success[答案]
考虑到 i 不是常数我们考虑需要将其消成常数，而唯一常数与 i 有关只有 n （2^i 这里没法化简 \times i ），所以考虑吸收率。
然后用二项式定理即可。
\sum_{i = 0} ^ n \dbinom{n}{i} \times i \times 2^i = \sum_{i = 0}^{n} \dbinom{n - 1}{i - 1} \times n \times 2^i \qquad 这里是吸收率
\\
= 2 \times n \times \sum_{i=0}^{n-1} \dbinom{n-1}{i} 2^i \qquad 提出公因数\,n\,并提出一个\,2\,使其变成二项式定理形式
\\
= 2n \times 3^{n-1} \qquad 后面可以看成 \, 2^i \times 1^{n-1-i}，即\, (2+1)^{n-1}，即 3^{n-1}
:::
一些式子
上指标求和：\displaystyle \sum_{i=0}^{n} \dbinom{i}{m} = \dbinom{n+1}{m+1}
:::info[证明]
考虑数学归纳法。
我们将 \dbinom{n+1}{m+1} 改成递推形式分解，则有：
\begin{aligned}
\dbinom{n+1}{m+1} &= \dbinom{n}{m+1} + \dbinom{n}{m}
\\
&= (\dbinom{n-1}{m+1} + \dbinom{n-1}{m}) + \dbinom{n}{m}
\\
&= \cdots
\end{aligned}
可见，如此分解下去，我们将会有 \dbinom{-1}{m+1} + \dbinom{-1}{m} 因为 n 是有限的，所以我们再向下拆解也没有意义。
所以综合下来有：
\begin{aligned}
\dbinom{n+1}{m+1} &= \dbinom{n}{m} + \dbinom{n-1}{m} + \cdots + \dbinom{0}{m}
\\
&= \sum_{i=0}^n \dbinom{i}{m}
\end{aligned}
证毕。
:::
平行求和法：\displaystyle \sum_{k=0}^n \dbinom{r+k}{k} = \dbinom{r+n+1}{n} 其中 r,n 给定。
:::info[证明]
我们要想办法将其表示为上指标求和的表示手段。
考虑到 k<0 是没有意义的，所以我们加入多少个 k<0 都不会对答案有影响，那我们就将 k 的值域设为 [-r,n] ，式子就转变为 \displaystyle \sum_{k=-r}^n \dbinom{r+k}{k} 。
然后我们要用上指标求和，下面就得是一个常数，所以式子变成 \displaystyle \sum_{k = -r}^n \dbinom{r+k}{r} 。
这就是一个上指标求和的形式，套用公式，得：
\displaystyle \sum_{k=0}^n \dbinom{r+k}{k} = \dbinom{r+n+1}{r+1} = \dbinom{r+n+1}{n}
证毕。
:::
例题 ：\
化简 \displaystyle \sum_{k \le n} k \dbinom{r+k}{k} ，其中 r,n 给定。
:::success[答案]
我们发现 k 我们是不确定的，考虑使用吸收率，式子变成 \sum_{k \le n} (r+k) \dbinom{r+k-1}{k-1} 。
好像没有什么化简方向了。考虑转换一下式子：
发现 $r+k$ 和上面得 $r+k-1$ 相对应，我们考虑整出来一个 $\frac{1}{r+1}$ 给他吸回去，那么就提出一个 $r+1$，式子变成 $(r+1)\sum_{k \le n} \frac{r+k}{r+1} \dbinom{r+k-1}{r} = (r+1) \sum_{k\le n} \dbinom{r+k}{r+1}$。
化用上指标求和，得：$(r+1)\dbinom{r+n+1}{r+2} = (r+1) \dbinom{r+n+1}{n-1}$。
:::
### 简单例子
主要是插板法的小应用。
1. 将 $n$ 个无差别的球放进 $k$ 个不同的盒子，要求盒子非空。
:::info[封闭形式]
考虑插板法，我们把 $k$ 个盒子看成板子，将球放入盒子就是将板子插入球的空隙中。
因为盒子一定非空，所以球能放的空隙只有 $n$ 个，开头那个空隙不能放。然后我们要让最后一个板子一定在最后一个空隙，这样才能保证最后一个盒子非空。
所以现在我们只有 $k-1$ 个板子，$n-1$ 个空隙。考虑 $k-1$ 个板子分别放入 $n-1$ 个空隙的方案数，即为 $\dbinom{n-1}{k-1}$。
:::
2. 将 $n$ 个无差别的球放入 $k$ 个不同盒子，盒子可空。
:::info[封闭形式]
仍是插板法。
发现盒子可空并不好想。但是我们有盒子非空的基础。考虑转换成盒子非空。
那就让每一个盒子建一个“虚球”，这样每个盒子就必须放入一个球，那现在球的总数就是 $n+k$，此时的方案数就是 $\dbinom{n+k-1}{k-1}$。
:::
### 容斥原理
即若干集合的并可以转化为若干集合的交。
$$\left\vert \bigcup_{i=1}^n A_i \right\vert = \sum_{S \subseteq [[1,n]],S \neq \varnothing} (-1)^{\left\vert S \right\vert - 1} \left\vert \bigcap_{i \in S} A_i \right\vert$$
对于集合大小相同的情况我们有：
$$\left\vert \bigcup_{i=1}^n A_i \right\vert = \sum_{k=1}^n (-1)^{k - 1} \dbinom{n}{k} \left\vert \bigcap_{i =1}^k A_i \right\vert$$
其中 $\left\vert S \right\vert$ 表示集合 $S$ 的大小。
### 范德蒙德卷积
$$
\sum_k \dbinom{r}{k} \dbinom{s}{n-k} = \dbinom{r+s}{n}
$$
其中 $r,s,n$ 给定。
:::info[证明]
考虑组合意义。
也就是一个盒子里有 $r$ 个红球，$s$ 个蓝球，在其中取 $n$ 个的方案数。
就是在其中取 $k$ 个红球，取 $n-k$ 个蓝球的方案数，其加起来就是 $r+s$ 个红蓝球里选 $n$ 个球的方案数。
:::
### 二项式反演
一般形式：
$$
f(n) = \sum_{i=0}^n (-1)^i \dbinom{n}{i} g(i) \Leftrightarrow g(n) = \sum_{i=0}^n (-1)^{n-i} \dbinom{n}{i} f(i)
$$
什么是反演？其实就是将上式看成关于 $g(i)$ 的方程组，解方程的过程就是反演。
其他形式：
$$
f(n) = \sum_{i = 0}^n \dbinom{n}{i}g(i) \Leftrightarrow g(n) = \sum_{i = 0}^n (-1)^{n-i} \dbinom{n}{i} f(i)
$$
一般应用于至多、至少、钦定和恰好的转变。
比如 $g(i)$ 为至多 $i$ 个符合条件的方案数，$f(i)$ 为恰好 $i$ 个符合条件，就有 $g(i) = \sum_{j = 0}^i \dbinom{i}{j} f(j) \Leftrightarrow f(i) = \sum_{j=0}^i (-1)^{i-j} g(j)$。
若 $g(i)$ 为至少，$g(i) = \sum_{j=i}^n \dbinom{j}{i} f(j) \Leftrightarrow f(i) = \sum_{j=i}^n (-1)^{j-i} \dbinom{j}{i} g(j)$。
若是 $f(n)$ 为钦定选 $n$ 个，$g(n)$ 为恰好选 $n$ 个，则有 $f(n) = \sum_{j=n}^m \dbinom{i}{n} g(i)$，其中 $m$ 为数量上界。所以 $f(n)$ 不能理解成普通的后缀和。
#### 例题
[P5505 [JSOI2011] 分特产](https://www.luogu.com.cn/problem/P5505)
题意：
> 给 $m$ 种特产，每种 $a_i$ 个，$n$ 个同学，每个人至少一个特产，问方案数。\
> 其中 $n,m,a_i \le 1000$。
::::info[tips]
:::info[trick]
对于时间上同时存在的物品，其方案数可以视为对每一种物品做一遍插板法，但允许有空隙，然后将结果乘回去。
:::
:::info[tip1]
考虑能否二项式反演以此来用恰好完成钦定。
:::
:::info[tip2]
考虑到设特产并不好做，那就设人，或者说我们可以将人看成盒子，特产看成小球去做插板。
:::
:::success[答案]
将人看成盒子，特产看成小球去做插板法。\
考虑令 $f(i)$ 为恰好 $i$ 个盒子是空的，$g(i)$ 为钦定 $i$ 个盒子是空的。
则有 $\displaystyle g(i) = \sum_{j=i}^n \dbinom{j}{i} f(j) \Leftrightarrow f(i) = \sum_{j=1}^n (-1)^{j-i} \dbinom{j}{i} g(j)$。
我们可以用隔板法得到 $\displaystyle g(i) = \dbinom{n}{i} \prod_{j=1}^m \dbinom{a_j+n-i-1}{n-i-1}$。
:::
::::
### 错位排列问题
问题形式：求长度为 $n$ 的排列 $a$ 有多少种排列方式使得恰好有 $k$ 个位置有 $a_i=i$，其中 $k \in [[0,n]]$。
错位排列问题总共有三种推法，分别是递推，容斥，二项式反演。这里介绍这三种推法。
#### 递推公式
考虑 $m=0$ 的情况。
设答案为 $d_n$，考虑 $a_k=n$ 的分类讨论。
- $k \neq a_n$，那我们就将 $a_k,a_n$ 互换后删去 $a_n$，实现 $n-1$ 的错位排列，而这样的 $k$ 有 $n-1$ 种，共 $n-1$ 种可能。
- $k = a_n$，那我们就将 $a_k,a_n$ 都删去，并且将大于 $a_k$ 的数都减 $1$，实现长度为 $n-2$ 的错位排列，这样的 $k$ 也有 $n-1$ 种可能。
综上，对于 $m = 0$ 的情况，我们有递推式 $d_n = (n-1)(d_{n-1} + d_{n-2})$。
对于 $m \neq 0$ 的情况我们就相当于从 $n$ 个数里选 $m$ 种可能，有 $\dbinom{n}{m} d_n$。
#### 容斥原理推错位排列公式
依旧默认 $m=0$。
设 $A_i$ 为 $a_i = i$ 的排列组成的集合，则不满足条件的排列构成的集合为 $\bigcup_{i=1}^n A_i$，根据组合意义，$|\bigcap_{i \in I} A_i|$ 即表示除了 $I$ 内元素以外的数构成全排列的数量，即 $(n-|I|)!$。
代入容斥原理公式有：$d_n = n! - \sum_{k=1}^n \dbinom{n}{k} (-1)^{k-1} (n-k)!$。
对于 $m \neq 0$ 的答案和递推答案一样。
#### 二项式反演推错位排列公式
考虑使用二项式反演。
令钦定 $i$ 个人得到自己帽子的方案数为 $f(i)$，恰好有 $i$ 个人得到了自己的帽子的方案数为 $g(i)$。可知 $f(i) = \dbinom{n}{i}(n-i)!$。而只有对于 $i \le j$ 的 $g(j)$ 对 $f(i)$ 有贡献，则有 $f(i) = \sum_{j=i}^n \dbinom{j}{i} g(j)$，根据二项式反演 $g(i) = \sum_{j=i}^n (-1)^{j-i} f(j)$。
可以发现和容斥原理推导是差不多的。
### 一些 tips
1. 对于组合数 $\dbinom{n}{k}$ 在 $n$ 大的时候可以把它看作关于 $n$ 的 $k$ 次多项式，这时候可以拉格朗日插值，有奇效。
2. 在求和的过程中要注意多项式定理的形式，例如 $n$ 为模数的级别，我们要尽量用多项式定理把 $n$ 变为模数，多项式定理即二项式定理的推广，即 $\displaystyle (x_1+x_2+\cdots+x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} \dbinom{n}{k_1\,k_2\,\cdots\,k_m}x_1^{k_1}x_2^{k_2} \cdots x_m^{k_m}$。
其中 $\displaystyle \dbinom{n}{k_1\,k_2\,\cdots\,k_m}= \frac{n!}{k_1!k_2! \cdots k_m!}$ 为多项式系数即多元组合数。
### 卡特兰数
其满足如下递推关系：
$$
C_n =
\begin{cases}
1 & n = 0
\\
\sum_{i = 0}^{n-1} C_iC_{n-i-1} & n > 0
\end{cases}
$$
卡特兰数有天然递归结构以至于其可以应用于多个问题，这里给出几种结构，如果有没有的读者可以自己参照 [OIwiki](https://oi-wiki.org/math/combinatorics/catalan/)。
#### 一般例题
1. 求 $n$ 个元素顺序入栈的合法出栈序列有多少种。
:::info[如何转换的]
设答案为 $C_n$，我们枚举 $1$ 的出栈时刻，设第一个元素第 $k$ 个出栈，则 $[[2,k]]$ 一定在 $1$ 之前出栈， $[[k+1, n]]$ 在 $1$ 之后出栈。
前一部分出栈序列有 $C_{k-1}$ 种，后一部分出栈序列有 $C_{n-k}$ 种。
则有递推式 $C_n = \sum_{k=1}^n C_{k-1} C_{n-k}$。
这和卡特兰数的递推公式相像。
:::
2. 求将 $2n$ 边形的顶点连成 $n$ 对，使任意两条连线不相交方案数。
:::info[如何转换的]
设答案为 $C_n$，枚举 $1$ 连向的顶点。
如果 $1$ 和 $2k$ 相连，则接下来只能在 $[[2, 2k-1]]$ 和 $[[2k + 1, 2n]]$ 之间连线，这两个也是分别 $C_{k-1},C_{n-k}$。
则有递推式 $C_n = \sum_{k=1}^n C_{k-1} C_{n-k}$。
:::
其他的表现形式还有：
1. $n$ 个点的有序二叉树个数
2. 长为 $2n$ 的合法括号序列数量
3. 从 $(0,0)$ 点向右或向上走到 $(n,n)$ 不越过对角线 $y = x$ 的方案数。
4. 将 $n$ 个红点与 $n$ 个黑点排成一排，使得任意一个 $k$，前 $k$ 个点中红点数不少于黑点数。
#### 封闭形式
我们考虑从表现形式推出来。
这里我使用其他表现形式的第 $3$ 个推出来。
可见我们从 $(0,0)$ 走到 $(n,n)$ 要走 $2n$ 步，向右走 $n$ 步的方案数即 $\dbinom{2n}{n}$（在总共 $2n$ 步里选其中 $n$ 步向右走），若穿过对角线，我们就把向上的变成向右，向右的变成向上，可见这样我们向上少走一步，到达了 $(n+1,n-1)$ 点。
这样的不合法的方案数是 $\dbinom{2n}{n-1}$。
则有 $\displaystyle \dbinom{2n}{n} - \dbinom{2n}{n-1} = \frac{1}{n+1} \times \dbinom{2n}{n}$。
### 斯特林数
#### 第一类斯特林数
第一类斯特林数 $\left[ n \atop k \right]$ 表示将 $n$ 个元素排成 $k$ 个轮换的方案数。\
其中轮换指圆排列，即 $a_1a_2a_3 \rightarrow a_2a_3a_1 \rightarrow a_3a_2a_1$。
其递推式子为 $[{n \atop k}] = (n - 1)[{n-1 \atop k}] + [{n-1 \atop k-1}]$。
其中两个转移分别表示：在环中插入一个位置，新增一个环。
#### 第二类斯特林数
第二类斯特林数 $\{{n \atop k}\}$ 表示将 $n$ 个元素划分为 $k$ 个子集的方案数。
其递推式为 $\{{n \atop k}\} = k \times \{{n-1 \atop k}\} + \{{n-1 \atop k-1}\}$。
其中两个转移分别表示：在子集后面插入一个数，新增一个子集。
其通项公式为 $\displaystyle \{{n \atop m}\} = \frac{1}{m!} \sum_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n$。
:::info[推导过程]
考虑其组合意义，$n$ 个不同小球放入 $m$ 个相同盒子，盒子非空总方案数。
盒子非空需要二项式反演，我们从容斥角度出发，考虑先让盒子不同，后面我们乘 $\frac{1}{m!}$ 就可以将其贡献减去。然后我们钦定有 $k$ 个盒子是空的，因为我们要求没有盒子空的，所以容斥系数即 $(-1)^k$，此时有 $\dbinom{m}{k}$ 中方案，生下来就可以随便放，即 $(m-k)^n$。
故有 $\displaystyle \{{n \atop m}\} = \frac{1}{m!} \sum_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n$。
当然，也可以用反演推导。
:::
#### 幂形式转化
第二类斯特林数的一个重要应用就是降幂。\
其有以下公式：
$$
\begin{aligned}
x^n &= \sum_k \{{n \atop k}\} x^{\underline{k}}
\\
x^{\underline{n}} &= \sum_k [{n \atop k}] (-1)^{n-k} x^k
\\
x^{\overline{n}} &= \sum_{k} [{n \atop k}] x^k
\end{aligned}
$$
考虑证明第一个式子。
::::info[证明]
:::info[组合意义]
左边的组合意义是 $n$ 个小球放入 $x$ 个不同盒子的方案数。
右边表示 $n$ 个不同小球放入 $k$ 个相同盒子而 $k$ 个盒子是从 $x$ 个不同盒子选出来的排列。
这两侧表示的组合含义相同，证毕。
:::
:::info[数学归纳证明]
我们有 $x^{n+1} = x \times x^n$，故有：
$$
\begin{aligned}
x^{n+1} &= x\sum_{k=0}^n \{{n \atop k}\}x^{\underline{k}}
\\
&= \sum_{k=0}^n \{{n \atop k}\}(x \times x^{\underline{k}})
\\
&= \sum_{k=0}^n \{{n \atop k}\} x^{\underline{k+1}} + \sum_{k=0}^n \{{n \atop k}\} k x^{\underline{k}}
\end{aligned}
$$
让前式 $j = k+1$ 后式 $j = k$，有：
$$
\begin{aligned}
x^{n+1} &= \sum_{j=1}^{n+1} \{{n \atop j-1}\} x^{\underline{j}} + \sum_{j = 0}^n \{{n + 1 \atop j}\} x^{\underline{j}}
\\
&= \sum_{j=1}^{n+1}(\{{n \atop j-1}\} + j\{{n \atop j}\}) x^{\underline{j}}
\end{aligned}
$$
括号里的正好是递推式，考虑合并，并且 $\{{n+1 \atop 0}\} = 0$，所以我们可以补 $0$ 项，则有：
$$
x^{m+1} = \sum_{j=0}^{n+1} \{{n + 1 \atop j}\} x^{\underline{j}}
$$
这正好是用 $n+1$ 表示的第一个式子，证毕。
:::
::::
#### 例题
[CF1278F Cards](https://www.luogu.com.cn/problem/CF1278F)
> 给 $m$ 张牌，其中有一张小丑牌，我们要进行 $n$ 次洗牌，每次洗完牌后会取出最上面的牌，$x$ 为从牌堆取出小丑的次数，所有排列等概率出现，求 $x^k$ 的期望。
>
> $k \le 10^4$，$n,m \le 998244352$。
~~明显我不会期望啊。~~
这个题有 $4$ 种做法，这里只介绍一种简单一点并使用降幂的做法。
::::success[答案]
:::info[trick]
对于一个游戏，其成功概率为 $p$，非成功概率为 $1-p$，则 $n$ 局赢 $k$ 局的概率为 $\dbinom{n}{k}p^k(1-p)^{n-k}$。
:::
:::success[answer]
有 $E[x^k] = \sum_{i=0}^n x^k p(x) = \sum_{i = 0}^n x^k \dbinom{n}{i}p^i(1-p)^{n-i}$。
考虑到后面是二项式定理的形式，我们可以思考化简，而斯特林数降幂转化成下降幂的形式，我们可以使用吸收率，则有：
$$
\begin{aligned}
\sum_{i=0}^n (\sum_{j=0}^k \{{k \atop j}\}i^{\underline{j}}) \dbinom{n}{i}p^i(1-p)^{n-i} &= \sum_{i=0}^n \sum_{j=0}^k \{{k \atop j}\}i^{\underline{j}} \dbinom{n}{i}p^i(1-p)^{n-i}
\\
&= \sum_{i=0}^n \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} \dbinom{n-j}{i-j}p^i(1-p)^{n-i}
\\
&= \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} (\sum_{i=0}^n \dbinom{n-j}{i-j}p^i(1-p)^{n-i})
\\
&= \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} (\sum_{a = 0}^{n-j} \dbinom{n-j}{a}p^{a+j}(1-p)^{n-a-j})
\\
&= \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} p^j (\sum_{a = 0}^{n-j} \dbinom{n-j}{a}p^{a}(1-p)^{n-a-j})
\\
&= \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} p^j 1^{n-j}
\\
&= \sum_{j=0}^k \{{k \atop j}\}n^{\underline{j}} p^j
\end{aligned}
$$
$O(k^2)$ 预处理第二类斯特林数即可。
:::
::::
### min-max 容斥
求一个集合的最值，我们可以用其子集与这个最值相反的最值求出，公式为：
$$\max S = \sum_{T \neq \varnothing,T \subseteq S} (-1)^{|T| - 1} \min T$$
注意 $T \neq \varnothing$，根据上述，$\max$ 和 $\min$ 交换也是可以的。
:::info[证明]
考虑一个集合中的数 $x$，设比 $x$ 大的数有 $k$ 个，则 $\forall T \subseteq S,T \neq \varnothing$ 的子集 $T$，考虑其中 $min T = x$ 的集合 $T$，枚举其集合大小，则总容斥数为 $\sum_{i=0}^k (-1)^i \dbinom{k}{i}$。容易发现（可以举几个例子）只有 $k=0$ 时才有贡献，其他的容斥数都为 $0$。而 $k=0$ 时就是 $\max S$。
:::
对于期望这个式子也是成立的，但是这里 $\max$ 表示满足所有条件时的期望，$\min$ 表示至少满足一个条件时的期望。
#### 例题
[HDU 4336](https://vjudge.net/problem/HDU-4336#author=translator:1281311:zh)
> $n$ 个物品，每个物品 $p_i$ 概率出现，也可能不出现，每个物品每次只能出现一个，求所有物品都出现的期望次数。
>
> $n \le 20,\sum_{i=1}^n p_i \le 1$。
::::info[tips]
:::info[经典模型]
期望的一个经典模型，若一个物品每天出现的概率为 $\frac{q}{p}$，则其期望 $\frac{p}{q}$ 天出现。
:::
:::info[tip]
$n$ 很小，考虑枚举子集用右式化为左式。
:::
:::success[answer]
令 $n$ 个物品组成的集合为 $S$，$S$ 中每一个元素表示第几次收集到的该物品。则所求为 $\max S$。
对其子集 $T$，$\min T$ 表示 $T$ 中物品第一次被收集到的次数，根据 min-max 反演推 $\max S$ 即可。
此时需要用到经典模型，$\frac{1}{\sum_{i \in T} p_i}$ 即为 $T$ 中物品第一次被收集到的次数。
:::
::::
# 线性代数
但是知周所众，线性代数完全没有我们 OI 学的这么简单，而本文这个部分只讨论线代有什么定理，在 OI 中如何使用，如果想要学习线性代数的**本质**，这里提供一个友联（虽然好像现在还没完工吧）：
[线性代数 -- 卡帕瓦KAPawa](https://www.luogu.com.cn/article/6vfv2xkz/)
## 向量
平面向量是必修二的内容，三维向量是选必一的内容。如果你已经学习了这些东西，可以跳过。
### 向量定义
1. 定义：有方向有大小的量叫做向量，物理中称矢量，但向量与矢量并不完全相同，不过基本相像。
有向线段顾名思义就是有方向的线段，在平面中，我们可以用有向线段表示向量。
2. 向量的记法：向量常记作 $\mathbf{a}$，即加粗的小写字母，但是在手写体中通常表示为 $\vec{a}$，这里我就表示为 $\mathbf{a}$ 了。
3. 如何表示向量：其可以表示为 $\mathbf{a} = (x,y,\cdots)$ 或 $\begin{bmatrix} x \\ y \\ \vdots \end{bmatrix}$，其还可以被表示为 $\mathbf{a} = (\theta, \psi, \cdots, r)$，可以把这种表示方法理解为向 $(\theta, \psi, \cdots)$ 方向走 $r$，即用向量的模长（就是向量的长度）和方向角表示这个向量，其中 $r$ 是向量的模长，$(\theta, \psi, \cdots)$ 是向量的方向角。
:::info[为什么向量可以用第一种表示方法]
***这是必修二的内容，如果想看这一部分内容请先将下面向量的基本运算看完。***
根据向量基本定理，我们可以知道平面中任意向量都可以被两个不共线的向量表示，而其推广到多维空间也是合法的。
所以我们可以用 $\mathbf{a} = (x,y,\cdots)$ 来表示向量 $\mathbf{a}$。
:::
### 向量的基本运算
#### 向量加法
定义 $\mathbf{a} + \mathbf{b} = \mathbf{c}$，已知 $\mathbf{a}$ 和 $\mathbf{b}$，则 $\mathbf{c}$ 可以被以下方式在平面中表示。
1. 三角形法则：将 $\mathbf{a}$ 的终点和 $\mathbf{b}$ 的起点重合，由 $\mathbf{a}$ 的起点连向 $\mathbf{b}$ 的终点，这个有向线段就是向量 $\mathbf{c}$ 的有向线段。
2. 平行四边形法则：令 $\overrightarrow{AB} = \overrightarrow{CD} = \mathbf{a},\overrightarrow{AC} = \overrightarrow{BD} = \mathbf{b}$，可以发现，这四条有向线段围成了平行四边形，而起点交汇处（点 $A$）和终点交汇处（点 $D$）的有向线段 $\overrightarrow{AD}$ 即为 $\mathbf{c}$ 的有向线段。
#### 向量的数乘
设 $x \in R$，则有 $x \mathbf{a}$ 也是一个向量，且与 $\mathbf{a}$ 相比，大小改变，当 $x > 0$ 时，$x \mathbf{a}$ 方向不变，当 $x < 0$ 时，$x \mathbf{a}$ 方向相反，当 $x = 0$ 时，$x\mathbf{a}$ 为零向量，方向任意。
#### 向量的点积（数量积）
定义两个平面向量 $\mathbf{a,b}$，其点积为 $\mathbf{a} \cdot \mathbf{b} = |\mathbf{a}||\mathbf{b}| \cos \theta$，其中 $|\mathbf{a}|$ 表示向量 $\mathbf{a}$ 的长度， $\theta$ 表示向量 $\mathbf{a,b}$ 的夹角大小。
这明显是个实数。
其是有几何意义的，是 $\mathbf{a}$ 在 $\mathbf{b}$ 上投影的长度与 $|\mathbf{b}|$ 的乘积。
其中 $\mathbf{a}$ 在 $\mathbf{b}$ 投影为设有向线段 $\overrightarrow{AB} = \mathbf{a}, \overrightarrow{AC} = \mathbf{b}$，过点 $B$ 向 $\overrightarrow{AC}$ 做垂线交 $AC$ 所在直线于点 $D$，则有向线段 $\overrightarrow{AD}$ 即为 $\mathbf{a}$ 在 $\mathbf{b}$ 投影的有向线段。
投影的大小就是 $\frac{\mathbf{a \cdot b}}{|\mathbf{b}|}$。
其存在一个重要~~吗~~的性质：$\mathbf{a} \perp \mathbf{b} \Leftrightarrow \mathbf{a} \cdot \mathbf{b} = 0$，其中我们认为 $\mathbf{0}$ 与任何向量垂直。
### 平面向量基本定理
若 $\mathbf{a,b}$ 为两个不共线的向量，则平面中所有向量都可以被 $\mathbf{a,b}$ 用数乘和加法表示。
这时向量 $\mathbf{a,b}$ 就叫做这一平面所有向量的基底。
通常我们令基底为互相垂直的向量，这叫做正交基，即 $\mathbf{a} \perp \mathbf{b}$，因为这样有 $\mathbf{a} \cdot \mathbf{b} = 0$，在向量的坐标表示中的点乘运算没有影响。
这个定理推广到 $n$ 维空间也是适用的。
### 向量坐标表示下的基本运算
一般我们令基底互相垂直，这里也是。
这里我们讨论平面向量，因为其推广到多维空间是相同的，所以这个平面的基底为 $(\mathbf{i,j})
首先我们要知道向量如何坐标表示：\
有 \mathbf{a} 使得存在 x,y \in R ，有 \mathbf{a} = x\mathbf{i} + y\mathbf{j} ，我们就可以用 \mathbf{a} = (x,y) 表示向量 \mathbf{a} （其实就是上面的表示方法）。
那么对于向量 \mathbf{a,b} ，其中 \mathbf{a} = (x_1,y_1), \mathbf{b} = (x_2,y_2) ，有 \mathbf{a+b} = (x_1+x_2,y_1+y_2) ，这个就是将 mathbf{a,b} 用基底表示后合并得到的。
也有 \mathbf{a \cdot b} = x_1x_2 + y_1y_2 ，也可以分解基底后合并得到。
还有 x \in R, x\mathbf{a} = (xx_1,xy_1) 。
什么？你告诉我不会减法？那不就是将 \mathbf{b} 整成方向与其相反的向量去求吗，也就是 \mathbf{a-b} = (x_1 - x_2,y_1 - y_2) ，其中 -\mathbf{b} = (-x_2,-y_2) ，这也叫相反向量。
向量的叉乘（向量积）
定义平面向量的叉乘为 \mathbf{a \times b} = x_1y_2 - x_2y_1 。
它的几何意义是两向量围成的平行四边形的有向面积 ，其绝对值等于三角形面积的二倍。
三维向量的叉乘（我也不会）结果就是一个新向量 ，同时垂直于 \mathbf{a,b} ，满足右手定则。
常用的性质：
共线或平行判断：\mathbf{a \parallel b} \Leftrightarrow \mathbf{a \times b} = 0 。
方向判断：叉积符号可以判断 \mathbf{b} 在 \mathbf{a} 的左侧还是右侧。
矩阵
矩阵的定义及其基本运算
矩阵的定义
有以下两种定义：
矩阵是由多个同维向量拼接成的矩形数表。在选定基后，它可以用来表示线性变换。
令 n,m \in N_+ ，由数域 F 中 n \times m 个数 a_{i,j} 排成的 n 行 m 列的图表叫做矩阵，可以用大写字母表示，也可以使用 A_{n\times m} 或 (a_{i,j}) 或 (a_{i,j})_{n \times m} 表示，其中第 i 行第 j 列的元素为 A_{i,j} 或 a_{i,j} 。
特别地，n 维向量可以看作 n \times 1 的矩阵，这也印证了第一个定义。
还有以下特殊矩阵：
其中若 n = m ，则称这个矩阵为 n 阶方阵。
零矩阵：满足 \forall 1 \le i \le n,1 \le j \le m,A_{i,j} = 0 ，常被记为 0 。
单位矩阵：主对角线上的元素均为 1 ，其他元素均为 0 的方阵 ，常被记为 I 。
矩阵的基本运算
矩阵加法：定义矩阵 C 是矩阵 A,B 的和，需满足 C_{i,j} = A_{i,j} + B_{i,j} ，矩阵加法必须满足 A,B 行列数相同。
矩阵数乘：定义 x \times A = B,x \in R ，需满足 B_{i,j} = A_{i,j} \times x 。
矩阵乘法：设有矩阵 A_{m \times p},B_{p \times n} ，则若有 C = A \times B ，需满足 C_{i,j} = \sum_{k = 1}^p A_{i,k} \times B_{k, j} ，其中 C 的大小 m \times n ，根据定义也可以看出其需要满足 A 的列数 = B 的行数 。\
其满足结合律但不满足交换律，而方阵 A 和与其同阶的单位矩阵 I 有 A \times I = I \times A = A 。
矩阵快速幂
首先求矩阵快速幂的矩阵一定是一个方阵。
因为矩阵乘法满足结合律，所以我们可以考虑求 A^k 时（其中 k 给定）将 A 看成一个元素，其他的普通快速幂没什么两样，不过我们刚开始的 res = 1 这个操作要变成生成单位矩阵了。
时间复杂度是 O(n^3 \log k) 。
:::success[矩阵的一般写法]
struct Matrix{
int a[N][N], n, m;
Matrix(){memset(a, 0, sizeof(a));n = m = 0;}//初始化
Matrix I(int x)
{
Matrix A;A.n = A.m = x;
for(int i = 1;i <= A.n;i ++) A.a[i][i] = 1;
return A;
}//生成单位矩阵
Matrix merge(Matrix A, Matrix B)
{
Matrix C;C.n = A.n;C = A;C.m = A.m + B.m;
for(int i = 1;i <= A.n;i ++)
for(int j = A.m + 1;j <= C.m;j ++)
C.a[i][j] = B.a[i][j - A.m];
return C;
}//合并两个矩阵
Matrix operator + (Matrix B)
{
Matrix C;C.n = n, C.m = m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
C.a[i][j] = a[i][j] + B.a[i][j];
return C;
}
Matrix operator * (int x)
{
Matrix C;C.n = n, C.m = m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
C.a[i][j] = a[i][j] * x;
return C;
}
Matrix operator * (Matrix B)
{
Matrix C;C.n = n, C.m = B.m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= B.m;j ++)
for(int k = 1;k <= m;k ++)
C.a[i][j] += a[i][k] * B.a[k][j];
return C;
}//有模数记得加取模
Matrix qpow(Matrix A, ll k)
{
Matrix res = I(A.n);
while(k)
{
if(k & 1) res = res * A;
A = A * A;k >>= 1;
}
return res;
}
};:::
矩阵加速
这一部分放在 DP 复习（我应该会写吧？），它确实和矩阵相关，但是这里不讨论这个。
高斯消元
求解 n 元一次方程组的解法。
对于 n 元一次方程组，易知我们只关注每个未知数对应的系数和常数项，所以我们把这些写成一个矩阵，这个矩阵我们称为增广矩阵，记作 [A|b] ，其中常数项列向量记作 b ，未知数系数组成的矩阵记为 A 。
则有：
[A|b] =
\begin{pmatrix}
\begin{array}{cccc|c}
a_{1,1}& a_{1,2} & \cdots & a_{1,n} & b_1
\\
a_{2,1} & a_{2,2} & \cdots & a_{2,n} & b_2
\\
\cdots & \cdots & \cdots & \cdots & \cdots
\\
a_{m,1} & a_{m,2} & \cdots & a_{m,n} & b_m
\end{array}
\end{pmatrix}
初等变换
我们进行高斯消元的时候是需要进行初等变换的，初等变换就是对增广矩阵做不改变其解的变换，当对行进行初等变换时，我们称这为初等行变换，列同理，有以下三种：
交换两行：交换矩阵的 i,j 行记作 R_i \leftrightarrow R_j 。
让某一行乘非零常数：让 i 行所有元素乘非零元素 k ，记为 R_i \rightarrow R_i \times k 。
让某一行 k 倍加到另一行：j 行 k 倍加到 i 行记作 R_i \rightarrow R_i + k \times R_j 。
值得一提的是，初等变换每一种都对应着一种矩阵，我们可以通过矩阵乘法来实现初等变换，而每种对应的是什么矩阵读者可以尝试自己列举，这个性质到后面较为重要 。
行阶梯形矩阵
高斯消元的目标是让增广矩阵化为行阶梯形矩阵，即每一行主元的左边都是 0 ，这样我们求出最后一行就可以代回求解。
即：
[A|b] =
\begin{pmatrix}
\begin{array}{cccc|c}
a_{1,1}& a_{1,2} & \cdots & a_{1,n} & b_1
\\
0 & a_{2,2} & \cdots & a_{2,n} & b_2
\\
\cdots & \cdots & \cdots & \cdots & \cdots
\\
0 & 0 & \cdots & a_{m,n} & b_m
\end{array}
\end{pmatrix}
矩阵的秩初步了解
如果你认为你会这里，可以跳转到矩阵的秩进一步了解。
我们现在先简单认为矩阵的行秩就是将矩阵简化为阶梯矩阵后非零行的数量，列秩同理。
其存在一个性质：行秩=列秩。\
行秩列秩统称为矩阵的秩。
为什么要了解这个呢？因为这是判断矩阵有无解的重要工具。其分为以下三种情况：
无解：系数矩阵的秩小于增广矩阵的秩，即存在 0 = 非零常数 的情况。
无数解：系数矩阵的秩 = 增广矩阵的秩，但增广矩阵的秩小于 n ，即存在 0 = 0 。
唯一解：系数矩阵的秩 = 增广矩阵的秩 = n 。
高斯消元的过程
高斯消元分为两步：前向消元，回代求解。
前向消元
对于第 i 列，分为两步：
选主元，从第 i 行向下找绝对值最大的元素，这是为了避免浮点数误差，假设则个元素在第 j 行，交换 i,j 行，即初等变换第一个。
消去第 i 列下方的元素：对于第 j 列，计算 k = \frac{a_{j,i}}{a_{i,i}} ，令 R_j \rightarrow R_j - R_i \times k ，也就是 j 行的每一个元素减去对应的 i 行元素乘 k 。
回代求解
对于第 i 行，我们让 i + 1 \sim n 的所有未知数代入求解即可。
高斯-约旦消元
其思想使让每一次计算时主元的系数都是 1 ，然后让所有行主元系数 > 1 的让他减去主元行所有对应元素乘其主元的系数。这样我们系数矩阵就是一个单位矩阵，对应的常数项的值就是解。
例如，我们有 \begin{pmatrix} 1 & 2 & 3 \\ 2 & 2 & 4 \end{pmatrix} ，其中最后一列是常数项，我们来模拟这个过程。
开始我们让找主元不为 0 的，那第一行就可以，然后让所有数除以主元系数，所以第一行变成了 1 \ 2 \ 3 。
之后让所有行都进行减去操作，这里是第二行，即我们让第二行减去第一行的二倍，因为其对应的第一个未知数的系数是 2 ，则变成了 0 \ -2 \ -2 。
然后判断第二行，发现其第二个未知数系数不为 0 ，所以有唯一解，让其所有元素除以主元的系数，即除以 -2 ，变为 0 \ 1 \ 1 。
最后再让所有行进行减去操作，这里是第一行，即我们让第一行减去第二行的二倍，原因同理，则第一行为 1 \ 0 \ 1 。
可见最后矩阵变成了 \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix} ，可见，这里每个常数项就是每个行主元的解。
矩阵的逆
定义一个方阵 A ，则方阵的逆 A^{-1} 要满足 AA^{-1} \equiv A^{-1}A \equiv I \pmod p 。
考虑如何计算 A^{-1} ，我们先考虑，让 A 变为 I ，也就是让 A 进行高斯-约旦消元，而高斯-约旦消元涉及到的也就是初等变换，我们又知道初等变换可以表示矩阵乘一个矩阵的形式，所以我们有 AT_1T_2T_3\cdots T_k \equiv I \pmod p 。
那我们就在做高斯-约旦消元的时候记录其初等变换的矩阵就可以了，其实就是用一个矩阵记录它是如何初等变换的。
那我们就可以考虑让 [A|I] 来求，这样 I 就可以记录其初等变换，当我们让 A \rightarrow I 时，就有 [I|A^{-1}] 。
P4783 【模板】矩阵求逆。
:::success[代码实现]
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++) cin >> a[i][j];
a[i][i + n] = 1;
}
for(int i = 1;i <= n;i ++)
{
int p = 0;
for(int j = i;j <= n;j ++) if(a[j][i]){p = j;break;}
if(p == 0){cout << "No Solution\n";return 0;}
if(p != i) for(int j = 1;j <= 2 * n;j ++) swap(a[i][j], a[p][j]);
ll s = qpow(a[i][i], mod - 2);
for(int j = 1;j <= n * 2;j ++) a[i][j] *= s, a[i][j] %= mod;
for(int j = 1;j <= n;j ++)
{
if(i == j) continue;
s = a[j][i];
for(int k = 1;k <= n * 2;k ++) a[j][k] -= a[i][k] * s % mod, a[j][k] = (a[j][k] + mod) % mod;
}
}:::
线性基
首先是一些相关定义，这里的定义也可以发现和前面的向量定义有点关系。
线性相关：对于向量 x_1,x_2, \cdots ,x_n ，如果存在不全为 0 的序列 a ，使得 a_1x_1+a_2x_2+ \cdots a_nx_n = 0 ，则称 x_1,x_2,\cdots ,x_n 是线性相关的。
线性基：从 x_1,x_2, \cdots ,x_n 中选出一个最大的子集，使得他们线性无关，则称这组向量为极大线性无关，也称基底，线性基。
向量空间：所有能由基底线性组合的向量构成了一个向量空间，又称线性空间。\
其拥有一个重要的性质（其实也就是平面向量基本定理的推广啦）：对于 k 维空间中的向量，如果刚好存在 k 个线性无关的向量 x_1,x_2, \cdots ,x_k ，则它们可以表示出所有 k 维空间中的向量，也就是说他们的向量空间为整个 k 维空间。
那到了现在我们似乎还是不会求线性基，莫慌，我们先考虑一些特殊版本，并且读者也可以猜一下线性基是干什么用的。
异或空间线性基
定义：在只有异或运算意义下的线性基，通俗来讲，有一个序列 A 和 B ，若 A 中所有数进行异或操作得到的集合 A' ，和 B 中所有数进行异或操作得到的集合 B' ，有 A' = B' ，且满足序列 B 线性无关，我们就称序列 B 是序列 A 的一组异或空间线性基。
通常情况下，我们求解线性基会采用高斯-约旦消元，因为其计算出的单位矩阵有更强的性质，其中有一个显然的事情是一个序列对应的异或空间线性基可能不止有一个，以下我们讨论的性质单位矩阵均可以升任，朴素的上三角矩阵不一定满足，但有些时候上三角矩阵还是比较好的。\
这里的单位矩阵指：对于所有的非自由变元（这一行主元的系数不为 0 ），要满足单位矩阵的性质，但对于所有自由变元（这一行主元的系数为 0 ）只需满足上三角矩形限制的矩阵。
所以其满足以下性质：
最大的异或值等于线性基中所有数的异或（仅单位矩阵）。
第 k 小的异或值等于其二进制位为 1 的线性基中的数的异或和（仅单位矩阵，小数对应低的位置，若未能成功插入要补 0 ）。
这就是异或空间线性基的所有性质，其实实数范围的线性基也满足这些性质。
所以线性基就可以完成对于一个序列的多个数，插入并判断，查询第 k 小，查询最值的操作。
而异或空间线性基的代码也是肥肠的好写，因为线性基的代码基本只需实现一个插入，后面用你维护的那个数组来查询即可，如果用高斯-约旦消元就把所有数读入之后统一插入即可，在线插入一般配合贪心使用。
P3812 【模板】线性基
:::success[核心代码]
bool insert(ll x)
{
for(int i = 62;i >= 0;i --)
if((x >> i) & 1)
{
if(!p[i]) {p[i] = x;return true;}
x ^= p[i];
}
return false;
}:::
P4570 [BJWC2011] 元素
这是相对于模板需要贪心的一个题，模板是要在最后逐个与线性基里的数判断异或的结果是否更大（因为我们最后不是单位矩阵），而这个题只需要先按照权值排序后判断能否插入来表示现在能否加上这个值即可。
正确性显然。
实数范围线性基
其实就是和上面一样的，只不过更像高斯-约旦消元一点而已，上面的性质在这里也是适用的，
P3265 [JLOI2015] 装备购买
和上面元素一样贪心就可以，把异或空间线性基改成实数的就可以了
:::success[核心代码]
bool insert(int id)
{
for(int i = 1;i <= m;i ++)
{
if(abs(a[id].a[i - 1]) > esp)
{
if(!p[i]) {p[i] = id;return true;}
long double s = a[id].a[i - 1] / a[p[i]].a[i - 1];
for(int j = 0;j < m;j ++) a[id].a[j] = a[id].a[j] - a[p[i]].a[j] * s;
}
}
return false;
}:::
矩阵的秩进一步了解
定义
设矩阵 A \in R_{n\times m} 由列向量 \vec{a_1},\vec{a_2}, \cdots ,\vec{a_m} 构成，他们的极大线性无关组 就是列秩 。由他们的线性组合构成的向量集合成为该矩阵的列空间 ，显然列秩就是列空间的维度数。同理的，行向量的极大线性无关组 就是行秩 ，行向量线性组合构成的向量集合为行空间 。
性质
任意矩阵的行秩等于列秩，所以我们可以把矩阵的秩记作 \textrm{r}(A) 或 \textrm{rank}(A) 。
还有一个显然的性质是初等变换不改变矩阵的秩 。
高斯消元求行秩的时候，行秩 = 主元数 = n\, - 自由元数。
:::info[为什么行秩等于列秩]
考虑对矩阵 A 做初等行变换 ，其不改变行空间，因此行秩不变，同时也不改变列空间之间的线性关系，因此列秩也不变。
形成行阶梯矩形后，非零行个数 r 就为行秩，而主元所对的列也为 r 个，因此行秩也为 r ，可得行秩 = 列秩。
:::
特殊情况
对于 A_{n \times m} ，如果 \textrm{rank}(A) = n ，则称 A 行满秩，若 \textrm{rank}(A) = m ，则称 A 列满秩。
特别地，对于方阵 A_{n \times n} ，若 \textrm{rank}(A) = n ，则称 A 满秩。
参考资料
数学知识（一）
基础数论（第一版）
二次剩余与高斯整数
大惊小跳算法和扩展大惊小跳算法
题解 P6091 【【模板】原根】
欧拉函数&莫比乌斯函数&狄利克雷卷积&杜教筛
莫比乌斯反演
浅谈线性代数合集
从高斯消元到行列式——线性代数进阶