杂项

一定要注意题面中的数据范围!!!!!

要注意判边界情况!!!尤其是 n=0,n=1,m=0,m=1,k=0,k=1n = 0, n = 1, m = 0, m = 1, k = 0, k = 1 这样的情况!!!

多项式

  • 想要分治 + NTT的话,就必须要把答案写成这样的形式: ans=iF(i)\displaystyle ans = \prod_{i} F(i)

    即每个F(i)F(i)的地位要等价,否则不行。一般就把阶乘除过去就可以了

莫队

先把序列分块,把询问重新排序:belong[l]belong[l]为第一关键字,rr为第二关键字

看到区间问题,不要求在线就要往莫队上想

似乎这样的带权莫队复杂度也是正确的:每个数有权值wiw_i,一个数被加入/删除的复杂度为O(wi)O(w_i),保证wi=O(n)\sum w_i = O(n)。分块时按wi\sum w_i分,一旦当前的wi\sum w_i超过lim(=m(wi))lim(= \frac{m}{\sqrt(\sum w_i)})就立刻新开一个块

感性理解复杂度很对,若一个块大小很大,那序列长度就会很小

奇偶优化

左端点在奇数块内的询问,按rr递增排序

左端点在偶数块内的询问,按rr递减排序

回滚莫队

当莫队维护的数据结构只能加入、撤销而不好删除时的做法

其实就是每次询问完之后左指针回滚(撤销)到询问左端点所在块的右边界,总复杂度还会是正确的

但其实如果只能删除而不好加入也可以这样做,把排序方式换一下即可

带修莫队

相当于是(l,r,t)(l, r, t)三维的莫队

增加一根时间轴(与序列轴分开),询问按ll所在块为第一关键字,rr所在块为第二关键字,tt为第三关键字排序

先把llrr移到当前询问位置,然后移时间。移动过程中遇到的修改就执行(往右则应用,往左则撤销)

具体而言,判断修改的点是否在当前[l,r][l, r]内,若在则直接在数据结构上应用,否则更改序列轴上的值

三元环计数

无向图

重新定向成有向图,从度数小的点往度数大的点连边 (从大往小也可以)

枚举每条边(x,y)(x, y),再枚举yy的所有出点zz,若存在边(x,z)(x, z)(x,y,z)(x, y, z)为三元环

一个三元环会且仅会在度数最小的点xx处被统计到

复杂度是m×degym \times \sum{deg_y}的,而因为每个yy点的出边都m\le \sqrt m(若>m> \sqrt m,那它相连的那些点的出边都>m> \sqrt m,矛盾),所以总复杂度为O(mm)O(m \sqrt m)

有向图

因为无向图三元环个数最多O(mm)O(m \sqrt m),所以每次搜出来一个三元环判在原有向图中是否存在即可

四元环计数

还是考虑在度数最小的点处统计,但是不能转有向图了

注意需要保证xx是度数最大的点。将所有点排序,只要不满足就立刻break,复杂度就对了

线段树

  • 需要维护区间所有数是否相等,可以通过维护min、max判断。位运算要判断每一位的话可以维护or、and

  • 区间修改可以往势能分析上想

最小树形图

性质: 对有向图中每个点取一条入边,构成的图若无环,则为树形图

贪心,每个点选最小的那条入边。若存在环则缩环,新图中连向环的边的权值要减去该点在环上的入边权值(反悔型贪心)

重复上述过程直到无环

虚树

每次把关键点提出来重构成树(保持原树中的形态)。这样就可以支持一些与关键点和树形态相关的操作。最简单的例如求某个点到其他所有点的最短路等

双端队列

  • 滑动窗口维护区间最值时,考虑用双端队列维护。这个队列还是一个单调队列,头部是最优的元素,往后依次变劣。因为每个元素出现的时刻是一段区间,所以要这样维护

  • 同理,斜率优化的某种情况也如此。头部的元素当前最优,但后面某个时刻会变劣

容斥

  • 考虑一些非常规(无法直接使用通式)的容斥时,回归容斥的本质,直接对于一个方案考虑它总共被统计了多少次,要怎样才能使这个次数恰好为1

考虑贡献

计数不好统计的时候一定要想到考虑贡献!!!!!

圆方树

将仙人掌转化成树

tarjan缩点双(仙人掌中点双一定是环),把环上的边全删掉,而所有环上的点与新点相连

原图的点称为圆点,新建称为方点。

  • 方点一定不相邻

  • 圆点可以与多个方点相连,但只会有一个方点父亲(即一个点可以作为多次割点,但最多作为非割点出现一次)。这个性质很重要

分块

  • 看起来很奇怪的数据结构操作要想到分块!!

  • 预处理块到块的信息当时间/空间较劣时,尝试用ST表预处理优化

长链剖分

优化DP

用指针写,重儿子的指针指向该点 + 1的位置;轻儿子的指针新开

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int fa[MAXN + 5], len[MAXN + 5], son[MAXN + 5];

inline void dfs (int x)
{
for (int y : G[x]) if (y != fa[x])
{
fa[y] = x;
dfs (y);
if (len[y] > len[son[x]]) son[x] = y;
}
len[x] = len[son[x]] + 1;
}

int pool[MAXN + 5], *F[MAXN + 5], *top = pool;
int ans[MAXN + 5];

inline void dfs (int x, int fg) // fg: 该点是否为重儿子
{
if (!fg) F[x] = top, top += len[x];
else F[x] = F[fa[x]] + 1;

F[x][0] = 1;

if (son[x])
{
dfs (son[x], 1);
if (ans[son[x]]) ans[x] = ans[son[x]] + 1;
}

int mx = 0;
for (int y : G[x]) if (y != fa[x] && y != son[x])
{
dfs (y, 0);
Chkmax (mx, len[y]);
for (int i = 1; i <= len[y]; ++i)
F[x][i] += F[y][i - 1];
}

for (int i = 1; i <= mx; ++i) if (F[x][i] > F[x][ans[x]] || (F[x][i] == F[x][ans[x]] && i < ans[x])) ans[x] = i;
}

O(nlogn)O(1)O(n\log n) - O(1)kk祖先

长剖性质:任意点的kk祖先所在重链长度k\ge k

若它和kk祖先不在同一条重链上,则中间分叉的另一颗子树的最大深度不会更小

20-5-19-1

字符串哈希

调试:把base设成10

群论

Burnside引理

比较广义的形式

等价类数目等于所有置换的不动点数的平均值

一个置换的不动点数为:有多少个方案应用该置换后不变

Polya定理

link

FWT

DWT(A)i=j=0n1fi,j×aj\displaystyle DWT(A)_i = \sum_{j = 0}^{n - 1} f_{i, j} \times a_j

构造系数

原理: ff需满足 fi,j×fi,k=fi,jk\displaystyle f_{i, j} \times f_{i, k} = f_{i, j \otimes k}

  • and\mathrm{and}: fi,j=[i&j=i]f_{i, j} = [i \& j= i](即[ij][i\subseteq j]
  • or\mathrm{or} : fi,j=[ij=i]f_{i, j} = [i | j= i](即[ji][j\subseteq i]
  • xor\mathrm{xor}: fi,j=(1)popcount(i&j)f_{i, j}=(-1)^{popcount(i\&j)}

验证: 若iji \subseteq j, iki \subseteq k,则i(j  k)i \subseteq (j~|~k),显然成立。其余两个类似

DWT(A)i=f0,0×DWT(AL)i+f0,1×DWT(AR)iDWT(A)i+n2=f1,0×DWT(AL)i+f1,1×DWT(AR)i \begin{aligned} DWT(A)_i&=f_{0,0}\times DWT(A_L)_i+f_{0,1}\times DWT(A_R)_i\\ DWT(A)_{i+{n\over 2}}&=f_{1,0}\times DWT(A_L)_i+f_{1,1}\times DWT(A_R)_i \end{aligned}

IDWT: 把上式改写成等式左边为AL,ARA_L, A_R的形式

以异或为例:

DWT(A)i=DWT(AL)i+DWT(AR)iDWT(A)i+n2=DWT(AL)iDWT(AR)i \begin{aligned} DWT(A)_i&=DWT(A_L)_i+DWT(A_R)_i\\ DWT(A)_{i+{n\over 2}}&=DWT(A_L)_i-DWT(A_R)_i \end{aligned}

则可解出

数论函数

一些关系

  • μ1=ϵ\mu * 1 = \epsilon

  • Id=φ1φ=μId\mathrm{Id} = \varphi * 1 \Rightarrow \varphi = \mu * \mathrm{Id}

  • (μ×Id)Id=ϵ(\mu \times \mathrm{Id}) * \mathrm{Id} = \epsilon (\Big(这是因为 dnμ(d)d(nd)=[n=1]\displaystyle \sum_{d|n} \mu(d)d(\frac{n}{d}) = [n = 1] )\Big)

一些结论

  • n>1n > 1时,i=1n[(i,n)=1]i=nφ(n)2\displaystyle \sum_{i = 1}^{n}[(i, n) = 1]i = \frac{n *\varphi(n)}{2}

    证明在这里

  • d(i×j)=xiyj[(ix,y)=1]\displaystyle \mathrm{d}(i\times j) = \sum_{x | i} \sum_{y | j}[(\frac{i}{x}, y) = 1]

    σ(i×j)=xiyj[(ix,y)=1]xy\displaystyle \sigma(i\times j) = \sum_{x | i} \sum_{y | j}[(\frac{i}{x}, y) = 1]xy

    证明很简单 首先xxyy相乘一定是i×ji\times j的约数,但直接统计会算重
    考虑i×ji\times j的某个质因数pkp^{k},若iipk1p^{k_1}jjpk2p^{k_2}k=k1+k2k = k_1 + k_2
    再考虑由等式右边得到的合法数字,设其含ptp^{t}
    因为保证了(ix,y)=1(\frac{i}{x}, y) = 1,所以当tk1t \le k_1时,它全部来源于ii; t>k1t > k_1时,ii一定对其贡献了pk1p^{k_1}
    因此每个ptp^{t}只会被算一次

Prufer序

一个长度为n2n - 2,权值在[1,n][1, n]的数组。与nn个点的有标号无根树一一对应

nn个点有标号无根树个数为nn2n^{n - 2}

度数

nn个点的度数已经确定,为degideg_i,则方案数为(n2)!i=1n(degi1)!\displaystyle \frac{(n - 2)!}{\sum_{i = 1}^{n}(deg_i - 1)!}

扩展

nn个带权aia_i的点,边的权值为连接两点点权之积,树的权值为所有边权值之积,则所有树的权值和为

(i=1nai)×(i=1nai)n2 \Big(\prod_{i=1}^{n} a_i\Big) \times \Big(\sum_{i=1}^{n}a_i\Big)^{n - 2}
  • ai=1a_i = 1时,即为nn2n^{n - 2}

  • nn个点被分成mm个联通块,第ii个联通块大小为sis_i,则把所有联通块连成树的方案数为(i=1msi)×nm2\displaystyle \Big(\prod_{i=1}^{m}s_i\Big) \times n^{m - 2}

DP

  • 多重背包二进制拆分优化

pb_ds

1
2
3
tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> T;
T.order_of_key (x);
T.find_by_order (k - 1);

vimrc/template 易错

  • exec "!g++ % -o %< " .a:str
  • y0 y1,不是y1 y2
  • 忘记#define DEBUG(x)

SAM

  • 记得背板子

  • 考虑SAM中每个节点对答案的贡献!!

概率和期望

D(X)=E(X2)E2(X)D(X) = E(X^2) - E^2(X)

网络流

遇到暴力都很难写的题要考虑网络流/费用流!!

Dijkstra 费用流

目标是使 disdis 非负,且不改变原本性质

给每个点赋一个顶标 hih_i,一条原本 (x,y,w)(x, y, w) 的边变为 (x,y,w+hxhy)(x, y, w + h_x - h_y)。每跑完一次dij后,就把 hih_i 加上这次的 disidis_i

真正的最短路是 hh 而不是 disdis

对偶

20-7-19-4

20-7-19-5