定理

推荐阅读： [矩阵树定理(+行列式) - command_block 的博客](https://www.luogu.com.cn/blog/command-block/ju-zhen-shu-ding-li-xing-lie-shi-post)。 ## 行列式 ### 定义 这个东西一般用于求解图的 ......

### 前言： 因为某次考试订正 T4，用到了 exCRT，然后发现我和 lws 不会 exgcd…… 所以来把 gcd 到 exgcd 重新学一下，就写了这篇 trick。 ### 欧几里得算法： 求证： $$ \gcd(a,b)=\begin{cases} \gcd(b,a\bmod b) & ......

## 逆元 求解$ax=b\pmod m$，其实等价于$ax+my=b$，然后扩欧就无了。 可以应用于求当是$a,p$互质，求$a$在模$p$意义下的逆元,方法就是求解$ax=1\pmod p$。 ## 中国剩余定理（CRT） ### 问题： 有$m_1,m_2,...,m_n$，$n$个整数两两互 ......

# 微分中值定理 ## 罗尔定理 ### 费马引理 $f(x)$ 在 $x_{0}$ $U(x_{0})$ 有定义，在 $x_{0}$ 处可导，如 $f(x)\le f(x_{0})$，所有的 $x\in U(x_{0})$。 则 $f'(x_{0}) = 0$。 导数等于零的点为函数的驻点（或稳定 ......

欧拉定理： 若$gcd(a,m)=1$，则$a^{\varphi(m)}\equiv1\pmod{m}$ 证明：令$r_1,r_2,···,r_{\varphi(m)}$为模m下的一个简化剩余系，则$ar_1,ar_2,···,ar_{\varphi(m)}$也为模m下的一个简化剩余系,令$f=r_ ......

[传送门](luogu.com.cn/problem/P4313) 数据范围一眼网络流。 考虑每个人文理只能选一个，考虑最小割。 考虑源点$S$向$(i,j)$连一条费用为$art_{i,j}$的边，$(i,j)$向汇点$T$连一条费用为$science_{i,j}$的边。若割$S$与$(i,j)$ ......

[toc] # 谱分解定理 设三阶**实对称矩阵** $A$，若矩阵 $A$ 的特征值为 $\lambda_1,\lambda_2,\lambda_3$，对应的特征向量分别为 $\alpha_1,\alpha_2,\alpha_3$ 且**两两正交**，则 $A = \lambda_1 \alpha ......

给定两个非负整数数列 $p_1 \ge p_2 \ge \dots \ge p_n$ 以及 $q_1 \ge q_2 \ge \dots \ge q_m$ 满足 $\sum_{i = 1}^n p_i = \sum_{i = 1}^m q_i$，存在一个简单二分图使得左部点的度数分别为 $p_1, ......

BEST 定理。 从 $s$ 出发的欧拉回路个数。选出一个内向树，对于 $u$ 指定父边作为从 $u$ 离开的最后一条边。再对所有节点剩余的出边随意定一个顺序，方案数是： $$ T_s\times out_s!\prod_{i\neq s}(out_i-1)! $$ 其中 $T_s$ 是 $s$ 为 ......

~~没有证明绝对不是因为我不会~~，证明可看:[重谈主定理（master定理）及其证明](https://www.cnblogs.com/GJY-JURUO/p/13719879.html) 这篇文章主要是写给自己看的，写的不好。 $$ \text{如果有} T(n)=aT(\lceil\frac{ ......

一、起源与发展 CAP（Consistency、Availability、Partition Tolerance）（一致性、可用性、分区容忍性）也叫Brewer定理，由Eric Brewer于2000年提出。 2002年，Seth Gilbert和Nancy Lynch用严谨的数学推理证明了CAP猜 ......

> **观前提醒**：「文章仅供学习和参考，如有问题请在评论区提出」 [toc] ## 前置 ### 剩余类（同余类） 给定一个正整数 $n$ ，把所有的整数根据**模 $n$ 的余数 $r\in [0, n - 1]$** 分为 $n$ 类，每一类就可以被表示为 $C_{r} = nx + r$ ......

威尔逊定理：若p为素数，则p可以整除(p-1)!+1。 用同余方程表示为：(p-1)! ≡ -1 (mod p) 证明如下 充分性： 当p=1时，(p-1)! ≡ 0 (mod p) 当p=4时，(p-1)! ≡ 2 (mod p) 当p>4时，当p为完全平方数时，设k²=p，探讨2k和p的大小，因 ......

lucas 定理用于求解模数很$**$的组合数求解，比如模小素数，会遇到不一定互质即没有逆元的情况。 $$ C_{n}^m\equiv C_{n/p}^{m/p}⋅C_{n\mod{p}}^{m\mod{p}}$$ 或者说 $(n_i,m_i)$ 是 $(n,m)$ 在 $p$ 进制上的一组，$C_ ......

组合意义天地灭。 ## Lucas 定理 > 问题 $1$：给定 $n, m \in \mathbb{N}$ 与 $p \in \mathbb{P}$，其中 $n$ 与 $m$ 相当大，而 $p$ 则相对较小，要求计算 $\binom{n}{m} \bmod p$ 的值。 一般的预处理逆元以及递推的 ......

 ![image](https://img2023.cnblogs.com/blog/1943217/2 ......

### 概念 用语言描述，容斥原理求的是不满足任何性质的方案数，我们通过计算所有至少满足 $k$ 个性质的方案数之和来计算。 同样的，我们可以通过计算所有至少满足 $k$ 个性质的方案数之和来计算恰好满足 $k$ 个性质的方案数。这样的容斥方法我们称之为广义容斥原理。 ......

**## Part 1：知识点 #### 费马小定理 若 $p$ 为质数，$a\perp p$，则 $a^{p - 1} \equiv 1 \pmod{p}$ #### 欧拉定理 若 $a\perp n$，则 $a^{\varphi(n)} \equiv 1 \pmod{n}$ （[不会欧拉函数的点 ......

**最长反链**：一张有向无环图的最长反链为一个集合 $S \subseteq V $，满足对于 $S$ 中的任意两个不同的点 $u, v \in S(u \ne v)$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$，且 $S$ 的大小尽量大 **最小不可重链覆盖**：在 DAG 中选出若干 ......

# 欧拉函数 **互质**：对于 $\forall a, b \in \mathbb{N} $， 若 $a, b$ 的最大公因数为 $1$ ， 则称 $a, b$ 互质。 **欧拉函数**:即 $ \varphi (N)$, 表示从 $1$ 到 $N$ 中与 $N$ 互质的数的个数。 在**算术基本 ......

Lucas定理： 主要是求$C_{n}^{m}$在模$p$情况下($mod \, p$)(一般$p$较小，而$n,m$较大的情况) 公式: $ C_{n}^{m} ≡ C_{n \, mod \, p}^{m \, mod \, p} \times C_{n/p}^{m/p} (mod \, p) ......

定义竞赛图的比分序列是将竞赛图每个点的出度从小到大排列得到的序列。 所谓兰道定理，即一个长度为$n$的序列$\{s_i\},s_i\le s_{i+1}$是合法的比分序列当且仅当$\forall k,\sum_{i=1}^ks_k\ge C(k,2)$ 进一步的一个竞赛图强连通的充要条件是：把它的所 ......

AcWing 204. 表达整数的奇怪方式 - AcWing 最近学了一下中国剩余定理，数论太深奥了，太难学啦，如果肯花时间还是可以学懂的，不过留给我的时间不多啦，只能学个大概，会用就行了，我在想为什么有的初中生、高中生编程能力以及逻辑思维能力都那么dior，我上初中和高中时，压根都不知道什么是编程 ......

（1）设dF12为电流元1给电流元2的力，I1和I2分别为他们的电流强度，dl1和dl2分别为两线元的长度，r12为两电流元的距离，则dF12的大小满足下列比式： 或 dF12的大小还与两电流元的取向有关。 （2）电流强度单位 （1）中dF12的单位为N=kg*m/s2，长度dl1、dl2和r12的 ......

由【物不知数】问题引入：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 意思就是有一个数满足除以3余2，除以5余3，除以7余2。 不过解法还挺公式化的，这里就用变量整理吧 x=a1(mod b1) x=a2(mod b2) x=a3(mod b3) M=b1*b2*b3，c1=M ......

# Burnside 定理 ## 问题： 给定一个 $n$ 个点，$n$ 条边的环，有 $m$ 种颜色，给每个顶点染色，问有多少种**本质不同**的染色方案，答案对 $10^9+7$ 取模 注意本题的本质不同，定义为：**只需要不能通过旋转与别的染色方案相同**。 ## 题目初步解读 我们考虑如果不 ......

分析复杂度时可能有用。（主定理狗都不学） 若有递归式 $T(n)=aT(\dfrac{n}{b})+f(n)$ 则分以下三种情况： + $f(n)=O(n^{\log _ b a-\epsilon}),\epsilon>0$，此时 $T(n)=\Theta(n^{\log_ b a})$ + $f( ......

结合 [图论中的概念与定义](https://www.cnblogs.com/Lkkaknoi/p/17524786.html) 食用更佳。 ## 网络流与二分图 - Konig定理：最小点覆盖 = 最大匹配（[proof](http://www.matrix67.com/blog/archives ......

归类为线性代数、图论。证明都是神仙，特别是名字带“理”的，不证了。 ## 行列式 ### 定义 行列式（Determinant）是对 $n$ 阶方阵 $A$ 定义的，是一个标量。$A$ 的 $n$ 阶行列式 $det(A)$ 或 $|A|$ 定义如下： $$det(A)=\sum_p(-1)^{\m ......

**一.公平组合游戏ICG：** 定义为: 1.有两名玩家交替行动 2.在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关 3.不能行动的玩家判负 **二.mex运算** 定义为: $mex(S) = min\{x\} (x \in N, x \notin S)$ 即为不属于集合$S$的最小 ......