跳转至

Welcome to Liam's Blog

  • 分类于 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，条件不变，递归构造即可。

  • 分类于 String
  • 需要 4 分钟阅读时间

后缀数组

后缀数组是处理字符串的利器。

定义

对于长度为 \(n\) 的字符串 \(s = s_1 s_2 \cdots s_n\)，定义 \(s[i,j] = s_i s_{i+1} \cdots s_j\)，即 \(s\) 的第 \(i\) 个到第 \(j\) 个字符形成的子串。

定义 sa 为 \(s\) 的后缀数组，sa[i] 表示第 \(i\) 小的后缀的编号。

定义 rk[sa[i]]=i，即 rk[i] 表示后缀 \(i\) 的 rank。

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

杂项

这里是一些杂七杂八的东西。

  • 分类于 Misc
  • 需要 2 分钟阅读时间

VSCode 配置

前言

作为 VSCode 资深用户，从第一次下载到如今，踩了一个又一个坑，在这里记录一下我的配置方法以及遇到的一些问题。

  • 分类于 GMOJ
  • 需要 2 分钟阅读时间

8113. 【2022.10.7联考noip模拟】Talulah

题意

给定长度为 \(n\) 的排列 \(p\)，定义集合 \(S_i = \{j \mid j \ge i \land \max_{k \in [i,j]} p_k = p_j\}\)。

给定 \(q\) 次询问 \(l,r\)，求 \(\sum_{x,y \in [l,r]} |S_x \cap S_y|\)。

\(n,q \le 2.5 \times 10^5\)

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

图论

这里是图论相关的算法笔记。