图论

网络流 / 费用流 / 二分图

建模时,可以往二分图上靠,以质因子、数、位置、路径和点(标记,两者选一) 等的奇偶性来进行划分。

最小链覆盖等于最大独立集等于 $n-$ 最大匹配。

链的边可以表示为 $(i,j)$ 的一种关系,通常为最小可重链覆盖,需要传递闭包。

$k$ 可重覆盖问题:$(l,r)$ 覆盖则 $l\rightarrow r$ ,$[l,r]$ 覆盖则 $l\rightarrow r+1$ 。

建图可采用倍增优化建图。

DAG

拓扑序,常与 $dp$ ,计数挂钩。

圆方树 / 仙人掌图 / 点双

转化成圆方树后,进行各种操作。

欧拉路径 / 回路

路径:在联通情况下,只存在两个奇度点。

回路:在联通情况下,只存在偶度点。

输出方案见博客。

分层图最短路、最短路优化

一般维护 $(c,d)$ 二元性质,正着建分层图,反着沿着分层图贪心跑,满足第一限制。

可以用二进制优化一些暴力。

技巧

若 $a\rightarrow b$ 表示 $a$ 存在某种关系变成 $b$ ,不妨当成 $a$ 是 $b$ 的一条有向边。

对于唯一对应的情况,是可以转换为基环树的。

构造

与进制有关,重心有关。

贪心分配颜色匹配方案(两两不同),直接从 $\frac{n}{2}$ 处断开即可。

数据结构

  • 如果遇到 $i-c_i$ 的询问,可以考虑离线或可持久化。
  • 两个区间内元素一致,可用并查集倍增优化。
  • 区间询问差分成单点询问。

DP

  • 注意决策单调性,尝试打表,可以用分治,单调队列等进行计算。
  • 状态压缩要考虑记录什么,什么会影响后面的统计。
  • 状态只和 已经确定好的数的信息(比如说值/位数/前几个数等)没有确定好的数字的位数 有关时,可以用数位 $dp$
  • 数位 $dp$ 要记录前面对后面的影响,如果影响相同,是可以记忆化的。
  • 计数 $dp$ 考虑从小规模滚到大规模。

数论

狄利克雷卷积

形式:$f*g=h$

$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

运算法则

$(f*g)*h=f*(g*h)$

$f*g=g*f$

$f*(g+h)=f*g+f*h$

常用数论函数

设正整数$n$按照算数基本定理分解质因数为 $n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$,

积性函数,$(a,b)=1,f(ab)=f(a)f(b)$

$\mu(n)=\begin{cases}0 & \exists i\in[1,m],c_i>1 \\1 &m\equiv 0(\operatorname{mod}2),\forall i\in[1,m],c_i=1\\ -1 &m\equiv 1(\operatorname{mod} 2),\forall i\in[1,m],c_i=1\end{cases}$

$d(n)=m$,即约数个数

$\sigma(n)=\sum_{d|n}d=\sum_{d=1}^n[d|n]d=\prod_{i=1}^m \frac{1-{p_{i}}^{c_{i}+1}}{1-p_i}$

完全积性函数,$f(ab)=f(a)f(b)$

$\epsilon(e)(n)=[n=1]$

$I(n)=1$

$id(n)=n$

卷积运用

$\mu*I=\epsilon$

$\varphi*I=id$

小性质

$~~~~~\varphi*I*\mu=id*\mu\\\rightarrow \varphi*\epsilon=id*\mu\\\rightarrow \varphi(n)=\sum_{d|n}\mu(d)\cdot \frac{n}{d}$

一类题 $\sum\limits_{i=1}^n\sum\limits_{j=1}^mw(i)w(j)f((i,j))$ ,通常都是找到积性函数 $g$ ,

使得 $f=g*I,g=f*\mu$ ,

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^mf((i,j))&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i\\d|j}g(d)\\&=\sum\limits_{d=1}g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}1\\&=\sum\limits_{d=1}g(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\end{aligned}$

约数 / 同余

裴蜀定理 $ax+by +cz = d$ ,最小正整数 $d$ 为 $\gcd$ 。

循环节大小为 $\text{lcm}(x,y)$ ,每次增长 $y$ ,$\text{mod } x$ 环长则为 $\frac{x}{\gcd(x,y)}$

同余最短路。

多项式

多项式牛顿迭代 :

$$ G(F(x))=G(F^*(x))+G'(F^*(x))(F(x)-F^*(x)) $$

组合数

$\sum\limits_{i=0}^m\dbinom{n}{i}=\dbinom{n+1}{m+1}$

$\sum\limits_{a} \dbinom{n}{a}\dbinom{m}{b-a}=\dbinom{n+m}{b}$

$\dbinom{n}{k}\dbinom{k}{m}=\dbinom{n}{m}\dbinom{n-m}{k-m},\dbinom{n}{k}k^{\underline{m}}-\dbinom{n-m}{k-m}n^{\underline{m}}$

$\dbinom{n}{k}\dbinom{n-k}{m}=\dbinom{n}{m}\dbinom{n-m}{k}$

斯特林数

$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$

$\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}$

$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{i=0}^m(-1)^{i}\dbinom{m}{i} (m-i)^n $

$k^n=\sum\limits_{m=0}^n \begin{Bmatrix}n\\m\end{Bmatrix}k^{\underline{m}}$

$k^{\underline{n}}=\sum\limits_{m=0}^n(-1)^{n-m}\begin{bmatrix}n\\m\end{bmatrix}k^m$

$k^{\overline{n}}=\sum\limits_{m=0}^n\begin{bmatrix}n\\m\end{bmatrix}k^m$

期望 / 概率

$E(aX+bY)=aE(X)+bE(Y)$ ,有线性性。

可以尝试差分求。

概率可以尝试前缀和求。

计数序列

Catalan

通项公式 $\frac{\tbinom{2n}{n}}{n+1}$

意义:与合法括号序列出栈入栈顺序构成双摄,即为 Catalan 。

划分数

$f_{n,m}=f_{n-m,m}+f_{n,m - 1}$

FWT

$i|j ,(0,0+1),(0,1-0)$

$i\& j, (0+1, 1),(0-1, 1)$

$i\text{ xor } j,(0+1,0-1),(\frac{0+1}{2},\frac{0-1}{2})$

子集卷积

多一维记录子集大小即可。

之后就是照常卷积。

生成树计数

$T = D-A$ 消掉一行。

有向图时,外向为 $D_{i,i}-A_{j,i}$ ,内向相反。

记得交换符号和乘上 $c$ 。

考前注意

文件名、freopen,子文件夹,return 0.

不要想“怎么做”,而是“我能找到哪些性质”用来结题。