模板
[TOC]
小技巧
位运算
- __builtin_ctz() 二进制末尾 $0$ 的个数
- __builtin_clz() 二进制前导 $0$ 的个数
- __builtin_popcount() 二进制中 $1$ 的个数
- __builtin_ffs() 二进制第一个 $1$ 的位置（从 $1$ 计数）
Python
读入一整行：
1 | a = list(map(int,input().split())) |
函数：
1 | def square(x) : |
数据结构
字符串
扩展KMP
1 | //求T与S所有后缀的最长公共前缀 |
Lyndon 分解
最小表示的初始位置为 $s+s$ 的Lyndon分解中字符串初始位置 $\le |s|$ 且最大的那个。
1 | //一个串是Lyndon串当且仅当该串字典序严格小于所有后缀 |
AC自动机
1 | queue<int> q; |
SAM
单个串的SAM
1 | namespace SAM { |
bfs建广义SAM
1 | namespace SAM { |
SA
SAIS - O(n)
1 | namespace SA { |
倍增 - O(n log n)
1 | inline bool cmp(int x,int y,int k){return t[x]==t[y]&&t[x+k]==t[y+k];} |
离线求区间 [l,r] 的border
1 | const int N=4e5+5; |
manacher
1 | void manacher(char *a, int *f) { |
PAM
1 | namespace PAM { |
猫树
1 | // O(n log n)预处理，O(1) 查询区间乘积 |
杨氏图表
插入一个数 $x$：
找到当前行中最小的比 $x$ 大的数 $y$：
- 若有，$x$ 将 $y$ 替换，往下一行插入 $y$；
- 否则将 $x$ 放置在最后一个位置，并结束。
Treap
1 | template<class T> |
LCT
1 | // LCT 维护最小生成树，维护子树和 |
KD-Tree
1 | struct point { |
左偏树
1 | int n; |
数学
数学公式
斯特林数
$ S_2(n,k) = S_2(n-1,k-1) + k S_2(n-1,k)$
$ S_2(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n$
$ S_1(n,k) = S_1(n-1,k-1) + (n-1) S_1(n-1,k) $
$ F_n(x) = \sum_{i=0}^n S_1(n,i) x^i = \prod_{i=0}^{n-1} (x+i) $
$ x^{\overline{n}}=\sum_{k} S_1(n,k)x^k $
$ x^n=\sum_{k} S_2(n,k) (-1)^{n-k} x^{\overline{ k } } $
$ x^{\underline{n}}=\sum_{k} S_1(n,k) (-1) ^ { n- k } x^k $
$ x^n=\sum_{k} S_2(n,k) x^{\underline{ k } } $
贝尔数
$B_{n+1} = \sum_{k=0}^n\binom{n}{k} B_k$
$B_n = \sum_{k=0}^n S_2(n,k)$
伯努利数
$S_m(n) = \sum_{k=0}^{n-1} k^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k}B_kn^{m+1-k}$
$B(x) = \sum_{i} \frac{B_i}{i!}x^i = \frac{x}{e^x-1}$.
快速乘
1 | inline ll mul(const ll &a,const ll &b,const ll &p) |
gcd & ex_gcd
1 | ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);} |
二次剩余
1 | namespace QuadraticResidue{ |
ex-CRT
1 | namespace CRT{ |
Miller_Rabin & Pollard-rho
1 | namespace Pollard_Rho{ |
Powerful Number
一个数 $n$ 满足 $\forall p((p\in \mathbb{P} \and p|n )\rightarrow p^2|n )$，则称 $n$ 为Powerful Number（简称PN）。
求出 $n$ 以内的PN数可以暴力搜索质因数。
假设我们要求 $\sum_{i=1}^nf(i)$，构造两个函数 $g,h$ 使得：
- $g$ 是积性函数。且 $g$ 的前缀和 $S_g(n)$ 容易求出。
- $\forall p\in \mathbb{P},g(p)=f(p)$。
- $f=g * h$。
那么，将原式变一变：
$$\sum_{i=1}^n f(i)\=\sum {i=1}^n\sum{d|i}h(d)g(i/d)\=\sum_{i=1}^nh(i)\sum_{j=1}^{n/i}g(j)\=\sum_{i=1}^n h(i)S_g(\left \lfloor \frac{n}{i} \right \rfloor)$$
可以发现 $f(p)=g(1)h(p)+g(p)h(1)=h(p)+g(p)$，又因为有 $g(p)=f(p)$，因此 $h(p)=0$。
显然 $h$ 是个积性函数，那么由积性函数的定义，对于 $h$ 的所有非 PN 数下标的取值均为 $0$。
我们只需快速求出所有 PN 数下标的 $h$ ，就可以了。
只需要求出 $h(p^k)$ 就可以了。这个可以通过推式子或者递推等解决。
类欧几里得
1 | struct Ans{ |
BSGS
1 | //y^x==z (mod p) −>x=? |
扩展Lucas
1 | inline pair<ll,ll> excrt(int n,ll *c,ll *m) { |
Min25筛
前提：积性函数；表示为 $\sum_{i\in \mathbb{P}}i^k$ 或 直接算；$f(p^k)$ 快速算。
$g(n,j)=\sum_{i=1}^{n}[i\in \mathbb{P} \text{ or }\min_i(p)> P_j]$
$$
g(n,j)=\begin{cases}
g(n,j-1) & \text{ if } P_j^2>n \newline
g(n,j-1)-P_j^k\left ( g(\left \lfloor \frac{n}{P_j} \right \rfloor,j-1)-g(P_{j-1},j-1) \right ) & \text{ otherwise }
\end{cases}
$$
$\sum_{i=1}^n[i\in \mathbb{P}]i^k=g(n,\pi( \left \lfloor \sqrt n\right \rfloor))$。
$$S(n,j)=\left ( g(n,\pi( \left \lfloor \sqrt n\right \rfloor)) \right )-g(P_{j-1},j-1))+ \sum_{k=j}^{\sqrt n}\sum_{P_k^{q+1}\leq n}(f(P_k^q)S(\left \lfloor \frac{n}{P_k^q} \right \rfloor,k+1)+f(P_{k}^{q+1}))$$
1 | const int N=1000000; |
Stern-Brocot树计算 d(n) 前缀和
1 | //时间复杂度O(n^{1/3} log n) |
O(1) 在线逆元
1 |
|
多项式
FWT
1 | void FWT_or(int *a,int opt) { |
FFT
1 | struct Com{ |
拆系数FFT
1 | const ll mo=1e9+7; |
NTT
1 | const ll mod=998244353; |
生成函数相关
图计数问题
以下问题，$n\leq 10^5$。模$998244353$。
带标号无向图数量
$f_i=2^{\binom{i}{2}}$
带标号无向连通图数量
设答案为$g_i$，其生成函数为$G$，第1题的生成函数是$F$，那么一个无向图就是由一些无向连通图组合起来的。
那么可以枚举一个无向图是由多少个连通图组成的，假设为$i$，那么答案跟$F^i(x)$所对应的系数有关系。因为无序，所以要除一个$i!$，因此有：
$F(x)=\sum_{i=0}^{\infty}\frac{G^i(x)}{i!}=e^{G(x)}$
同时求$\ln$得$G(x)=\ln F(x)$
多项式求$\ln$即可。
带标号DAG数量
很明显先dp，设$f_i$为$i$个点带标号的DAG数量。$f_0=1$。先假设有$j$个点度数为0，符合上述条件的$j$个点的集合有$\binom{i}{j}$个；这$j$个点可以任意向其他$i-j$个点连边，方案数有$2^{j(i-j)}$个；剩下的$i-j$个点也必须是个DAG，方案数为$f_{i-j}$乘法原理得方案数为$\binom{i}{j}2^{j(i-j)}f_{i-j}$，可是剩下的$i-j$个点中也还是有一些度数为0的点的，那么容斥一下就好了。
得到dp方程式：$f_i=\sum_{j=1}^i(-1)^{j-1}\binom{i}{j}2^{j(i-j)}f_{i-j}$
$$\frac{f_i}{(\sqrt{2})^{i^2}i!}=\sum_{j=1}^i\frac{(-1)^{j-1}}{(\sqrt{2})^{j^2}j!}\times \frac{f_{i-j}}{(\sqrt{2})^{({i-j})^2}(i-j)!}$$
设$F(i)=\frac{f_i}{(\sqrt{2})^{i^2}i!}$,$G(i)=\frac{(-1)^{i-1}}{(\sqrt{2})^{i^2}i!}(i\geq1)，G(0)=0$
那么$F=GF+1$，即$F=\frac{1}{1-G}$
多项式求逆，时间复杂度$O(n \log n)$
带标号的DAG数量，要求图弱连通
和第二题是一样的。设$H(x)$为该题答案的指数型生成函数，$F(x)$为第三题的指数型生成函数，那么$F(x)=e^{H(x)}$，$H(x)=\ln F(x)$，多项式求$\ln$即可。
拉格朗日反演
若两个函数 $F(x),G(x)$ 满足：$F(G(x))=x$。
则有：$[x^n]G(x)=\frac{1}{n}[x^{n-1}] (\frac{x}{F(x)})^n$
证明：懒得证了，会用就行。
线性代数
线性规划
单纯形法
1 | /* |
矩阵相关
1 | const int N=502; |
有向图两点间连通性问题(问删掉k个点后是否某两个点是否联通)
Yuhao Du Contest 11 Graph Problem：给定 $n$ 个点的图，每次问假设删掉 $k$ 个点 $p_1,p_2,\cdots,p_k$ 后， $w$ 对 $(i,j)$ 是否能从 $i$ 到 $j$。
对于邻接矩阵 $A$，能否从点 $i$ 到 $j$ 可以使用 $I+A+A^2+\cdots=(I-A)^{-1}$ 判断，由于不一定有逆，那么将 $A_{i,j}$ 随便设一个值，大概率下就有逆元了。更改 $k$ 行 $k$ 列对矩阵的影响不会太大，可以使用https://en.wikipedia.org/wiki/Woodbury_matrix_identity。
设 $M=(I-A)^{-1}$，$U_{i,j}=[i=p_j],V_{j,i}=A_{p_j,i}$。其中 $U$ 为 $n\times k$ 的矩阵，$V$ 为 $k\times n$ 的矩阵。
那么删掉这 $k$ 个点后的矩阵就是 $(I-A)+UV$。我们要判断这个矩阵的逆中某个位置是否相等，则有：
$(M^{-1}+UV)^{-1}=M-MU(I+VMU)^{-1}VM$。
化简后可得，只需判断 $M_{i,j}$ 与 $\sum_{1\le x,y\le k}M_{i,p_x}B_{x,y}^{-1}M_{y,j}$ 是否不相等即可。其中 $B_{i,j}=M_{p_i,p_j}$，为一个 $k\times k$ 的矩阵。
1 | int n,m; |
图论
KM算法
二分图带全匹配
1 | const int N=505; |
网络流
最小割
- 最小割输出方案，只需要从 $S$ 出发在残量网络上dfs，枚举每条边，如果两个点分属不同集合，则需要割掉。
Dilworth定理
- 偏序集中，最小链覆盖=最长反链，最小反链覆盖=最长链。
- 覆盖指的是若干集合，集合的并等于全集，任意两个集合的交为空。
- 最小链覆盖：把每个节点拆成入点和出点，对于原图中的两个点，连边 $(out_u,in_v)$，变成二分图最大匹配。
- 最小可重链覆盖：求出传递闭包后，变成最小链覆盖。
最大权闭合子图
- 闭合子图：对于一个图，图有点权。选择若干个点，若 $u$ 被选择，则所有 $(u,v)$ 的 $v$ 都要被选。
- 最大权闭合子图：点权和最大的闭合子图。
- 假设先全部选了正权点，那么如果存在一个负权点不选，但它的某个正权前驱选了，就不行。于是建立超级源汇 $S,T$，正权点连边 $(S,i,a_i)$，割掉表示不要这个正权点；负权点连边 $(i,T,-a_i)$，割掉表示选上这个负权点；原图边连 $(u,v,\infty)$。最后答案为所有正权点之和减去最小割。
混合图欧拉回路
一个由单向和双向边组成的混合图，你需要给双向边定向，使得定向后存在欧拉回路。
首先图要连通，不连通则一定不行。
先对双向边随意定向，统计 $d_i$ 为入度-出度。若 $d_i$ 为奇数则一定无解。
再弄一个超级源汇即可。
最大密度子图
每个边有边权，点有点权，要去选出一个子图，使得 $\frac{\sum_{i\in E}e_i}{\sum_{i\in V} v_i}$ 最大。
显然0/1分数规划，二分答案 $mid$，有：$\frac{\sum_{i\in E}e_i}{\sum_{i\in V} v_i}\geq mid$，即 $e-mid\times v\geq 0$。
一条边选了，则它的两个点都必须选。
十分像最大权闭合子图的形式！
对于原图的每条边看做一个点，做最大权闭合子图即可判断 $mid$ 是否合法。
上下界网络流
有上下界无源无汇可行流
对于一条边 $(u,v,l,r)$，我们强制让他流 $l$，剩下 $r-l$ 可以选择。设 $d_i$ 为 $i$ 点的所有入度-所有出度。若 $d_i>0$ ，则说明入度>出度，他要增加出度，因此连边 $(S,i,d_i)$；否则要增加入度，连边 $(i,T,d_i)$。
跑 $S\rightarrow T$ 的最大流，若 $S$ 所有出边（或 $T$ 所有入边）满流则有解。每条边的流量=下界+最大流中的流量。
有上下界有源有汇可行流
连边 $(t,s,\infty)$，变成有上下界无源无汇可行流。
有上下界有源有汇最大流
先求出可行流，然后去掉 $(t,s,\infty)$ 这条边，跑从 $s$ 到 $t$ 的最大流。最大流= $(t,s)$ 的流量+$s$ 到 $t$ 的最大流。
有上下界有源有汇最小流
先求出可行流，然后去掉 $(t,s,\infty)$ 这条边，跑从 $t$ 到 $s$ 的最大流。最小流= $(t,s)$ 的流量-$t$ 到 $s$ 的最大流。
消圈算法
1 |
|
Dinic
1 |
|
Dijkstra优化费用流
1 | namespace Graph{ |
K短路（可持久化可并堆优化）
1 | const int N=2.6e5; |
环计数，K4计数
1 |
|
弦图
$N(x)$，与 $x$ 直接相连的点集。
单纯点：${x}+N(x)$ 的诱导子图为一个团。
完美消除序列：$v_1,v_2,\cdots,v_n$，其中 $v_i$ 在 ${v_i,v_{i+1},\cdots,v_n}$ 中为单纯点。
1 | //v即为完美消除序列，pos即为点i在完美消除序列上的位置 |
最小树形图（朱-刘算法）
有向图，以 $rt$ 为根的最小生成树。$O(m \log n)$。
1 | int find(int x); |
带花树 $O(n^3)$
一般图匹配，不带权。
1 | namespace Graph{ |
SCC
求强连通分量
1 | void Tarjan(int u) { |
BCC
求点双、边双、圆方树。
1 | void dfs(int u) { |
树论
树哈希
1 | //必须想一种特殊的哈希函数乱搞。 |
虚树
1 | //虚树清空必须使用dfs清空所有东西，或者把虚树上所有节点记录下来。 |
点分治
1 | bool vis[N]; |
边分治
1 | //注意，边分治重构后，点数变成原来的两倍。 |
计算几何
1 | const db eps=1e-8; |