polya定理

树上启发式合并

虚树

CDQ分治

整体二分

无

见专题部分

AC 自动机

Educational Codeforces Round 92 (Rated for Div. 2) pro:3/3/7 rk:1823/15601

Codeforces Round #660 (Div. 2) pro:3/3/5 rk:1489/13591

洛谷p4980

Polya定理

给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案

首先由polya定理，首先存在 $n$ 个置换群，分别对应着旋转0个，旋转1个….旋转 $n-1$ 个。然后我们不难得知，若旋转 $k$ 个所对应的置换群为 $P_k$ ，那么 $C(P_k)=gcd(k,n)$

所以答案就是 $\frac{1}{n}\sum_{k=1}^{n}n^{\gcd(k,n)}$

转变成枚举 $gcd(k,n)$ ，上式可化为 $\frac{1}{n}\sum_{d|n}n^d\phi(\frac{n}{d})$

时间复杂度 $O(Tn^{\frac{3}{4}})$

Polya定理的模板题

洛谷p3233

虚树

给定一棵 $n$ 个节点的无根树，$q$ 次询问。

每次询问给定 $k_i$ 个关键点。树上每个节点属于离它最近的关键点(如果有多个距离最近点则选择编号最小的)。

每次询问要求输出 $k_i$ 个数，代表属于每个给定关键点的节点数。

强制以 $1$ 为根，转化为有根树。先考虑暴力 $\text{dp}$ 的做法。

在原树上，先一次 $\text{dfs}$ 找到每个节点子树方向上距离最小的关键节点，同时记录最小节点的距离和编号。

然后再一次 $\text{dfs}$ 更新每个节点祖先方向的距离最小的关键节点，即可得到答案。

暴力 $\text{dp}$ 对每次询问时间复杂度 $O(n)$。接下来考虑虚树优化 $\text{dp}$。

对虚树上的点，直接使用上述暴力 $\text{dp}$ 即可。关键在于如何计算不在虚树上的点对关键节点答案的贡献。

对于不在虚树上的点，要么位于虚树上的某个节点在原树上的儿子节点的子树中且该子树中没有关键节点，记为第一类点。

要么位于虚树上的某两个节点在原树上的路径上的某个节点的非路径方向的子树中，记为第二类点。

先考虑第一类点的贡献，发现第一类点可以全部计入它的第一个属于虚树的祖先节点的贡献中。

对于第二类点的贡献。取虚树上两相邻点在原树上的路径，可以根据到哪个关键节点近将路径分成两段。

每段路径上的节点及其非路径方向的子树对距离该节点近的关键节点做贡献，路径分界点可通过倍增查找。

时间复杂度 $O(\sum_{i=1}^q k_i\log k_i)$。

一道不错的虚树练习题。

P3796 【模板】AC自动机（加强版）

分类 ：AC 自动机

简要题意 ：有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 $T$ 中出现的次数最多。

解法 ：建出 Trie 图，对模式串结尾结点进行标记，BFS 求出 fail 指针，之后再遍历文本串，跑 Trie 图进行匹配，统计每个结点对应状态被匹配了几次。时间复杂度 $O(\sum|s_i|+|T|)$

评价 ：AC 自动机模板题。