跳转至

2025

  • 分类于 Math
  • 需要 1 分钟阅读时间

组合公式杂记

Raney 引理

对于长度为 \(n\) 的整数序列 \(x\) 满足 \(\sum x_i = 1\)，有且仅有其一个循环序列满足任意非空前缀和为正数（记作合法）。

  • 分类于 Math
  • 需要 3 分钟阅读时间

群论基础

定义

定义集合 \(G\) 与在 \(G\) 上的二元运算 \(\times\)，若其满足以下条件，则称 \((G,\times)\) 为一个群。

  1. 封闭性。\(\forall a,b \in G,a \times b \in G\)
  2. 结合性。\(\forall a,b,c \in G,(a \times b) \times c = a \times (b \times c)\)
  3. 单位元存在性。\(\exists e \in G,\forall a \in G,e \times a = a \times e = a\)
  4. 逆元存在性。\(\forall a \in G,\exists b \in G,a \times b = b \times a = e\)
  • 分类于 Record
  • 需要 1 分钟阅读时间

计数 DP 技巧

Cat Jumps

sort: 组合意义

将形如 \(\prod _{i=1} ^{n} (x+i)\)，其中 \(x = \sum_i^n a_i\) 的式子转化为对每个点连一条出边 \(j\)，权值为 \(c_i = a_j + [j \le i]\)，所有方案中边权乘积之和。这是因为 \(\sum \prod_i^n c_i = \prod_i^n \sum c_i\)，而一个 \(i\) 的所有方案中边权和恰为 \(i+\sum a\)，故相等。

之后用各类容斥技巧，以及第一、二类斯特林数进行计数。

  • 分类于 Math
  • 需要 3 分钟阅读时间

单位根相关

复数域下方程 \(x^n = 1\) 恰好有 \(n\) 个解，记 \(\omega_n = e^{\frac {2 \text{i} \pi} n}\)，则这 \(n\) 个解恰好为 \(1,\omega_n,\omega_n^2,\cdots,\omega_n^{n-1}\)。我们将 \(\omega_n\) 称作 \(n\) 次单位根。

在运算中，有 \(\omega_n = e^{\frac {2 \text{i} \pi} n} = \cos \frac {2 \pi} n + \text{i} \sin \frac{2 \pi} n\)。

特别地，在模 \(P\) 意义的数域下，有 \(\omega_n \equiv g^{\frac {P-1} n} \pmod P\)，其中 \(g\) 是模 \(P\) 意义下的原根。

  • 分类于 Theory
  • 需要 1 分钟阅读时间

定理

这里是一些常见的定理。

  • 分类于 Theory
  • 需要 1 分钟阅读时间

Hall 定理

定理内容

对于二分图 \(G=(V,E)\)，设其左、右部点集大小分别为 \(n,m(n \le m)\)。

对于左部点集的任意子集 \(S\)，定义其邻域 \(N(S)\) 为点集内点与右部点相连的点集，即 \(N(S) = \{v|\exists u \in S, (u,v) \in E\}\)。

则该图有完美匹配的充要条件为 \(\forall S,|S| \le |N(S)|\)。

证明

必要性显然，充分性可递归证明。

设当前左部点为 \(S\)，对于 \(u \in S\)，考虑为其寻找一个匹配点。

若 \(N(S\setminus \{u\}) = N(S)\)，任选 \(v \in N(S)\) 作为 \(u\) 的匹配点即可。

否则选择在 \(N(S)\) 中但不在 \(N(S\setminus \{u\})\) 中的点，这些点接下来也没法被匹配，所以不影响下面的过程。

于是我们将问题集合减小了 1，条件不变，递归构造即可。