Polya 定理学习笔记

这个东西其实之前一直想学但是咕咕咕了 233.

Burnside 引理

$ans = { 1 \over |G| } \sum_{f \in G} C(f)$ ,其中 $C(f)$ 表示置换 $f$ 中不动点的个数

Polya 定理

定义 $L(f)$ 为置换 $f$ 的循环节数,可以理解为对于任意一种状态至多经过 $L(f)$ 次置换 $f$ 可以变回原样。

易证置换 $f$ 的不动点一定满足其自身的循环节为 $L(f)$ ,即 $C(f) = k^{L(f)}$ ,其中 $k$ 表示颜色种数。

Polya 定理的公式即 $ans = { 1 \over |G| } \sum_{f \in G} k^{L(f)} $ 。

分治 NTT 学习笔记

memset0 又来水博客了…

第一种做法是正常的分治 NTT ,想必大家都会,就不废话了;
第二种做法是多项式求逆,想必大家也会,就摆几个式子了。

令 $F = \sum\limits_{x=0}^{\infty} x^i f_i$ , $G = \sum\limits_{x=0}^{\infty} x^i g_i$ ,则易得 $F * G = F - 1$ ,故 $F = (1 - G)^{-1}$ ,多项式求逆即可。

多项式求逆学习笔记

其实这玩意儿之前学过,不过感觉挺有趣的就再拿出来写篇笔记。

$$
\begin{align}
A B_n &\equiv 1 \pmod {x^n} \\
A B_{\frac n2} &\equiv 1 \pmod {x^{\frac n2}} \\
\\
B_n - B_{\frac n2} &\equiv 0 \pmod {x^{\frac n2}} \\
B_n^2 - B_n B_{\frac n2} + B_{\frac n2}^2 &\equiv 0 \pmod {x^n} \\
A(B_n^2 - 2B_n B_{\frac n2} + B_{\frac n2}^2) &\equiv 0 \pmod {x^n} \\
B_n &\equiv 2B_{\frac n2} - AB_{\frac n2}^2 \pmod {x^n}
\end{align}
$$

Min-Max 容斥学习笔记

感谢 lyc 哥哥上次给我讲了一下…然而我并没有听懂,只能自己再去学了一遍

Min-Max 容斥:

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
$$

可以用二项式反演证明:构造容斥函数 $f(x)$ 使得

$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|)
$$

考虑每个 $S’ \subseteq S$ 中 $\min(S’) = a_{x+1}$ 对答案的贡献为:

$$
g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)
$$

二项式反演得:

$$
\begin{aligned}
f(x + 1) &= \sum\limits_{i=0}^x (-1)^{x-i} {x \choose i} g(i) \\
\Rightarrow \ \ \ f(x + 1) &= (-1)^{x} \\
\Rightarrow \ \ \ f(x) &= (-1)^{x-1}
\end{aligned}
$$

所以:

$$
\begin{aligned}
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|) \\
&= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

二项式反演学习笔记

二项式反演:

$$
\begin{aligned}
f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i
\\
f_n=\sum_{i=0}^{n}{n \choose i} g_i
&\Leftrightarrow
g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}
$$

虚树学习笔记

题目先给定一棵树,然后每次询问和其中的一部分点有关的信息,且只考虑这些点和他们的 LCA 对答案没有影响,则可以考虑虚树。先求出所有点的欧拉序,把每次询问给出的点按照欧拉序排序,依次插入栈中,维护栈内元素使得形成一条在已插入的点中最右端的链。

其实没什么新知识,可以说是一种思想,所以代码也很好写,就是需要注意细节。

动态 DP 学习笔记

(好懒不想写博客)

把每个点的 dp 转移分成 重儿子 和 自己+轻儿子 两个部分。重儿子的转移把矩阵放树上维护,利用矩阵乘法的性质;轻儿子的转移的每次修改时暴力维护,利用 dp 的性质。详情参考 txc 哥哥的博客

圆方树学习笔记

圆方树可以解决仙人掌或一类无向图问题。

建树

通过 tarjan 缩点双为方点,原来的点为圆点。每个圆点连边到自己所属的点双方点,跨点双的圆点连边转换为圆方点之间的连边。

参考代码:

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
struct edge {
int tot, flag, hed[N], nxt[M], to[M];
edge () { tot = 2; }
void link(int u, int v) {
nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
}
} G1, G2;

void tarjan(int u, int father) {
++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
if (v != father) {
if (!dfn[v]) {
tarjan(v, u), low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
G2.link(u, ++tot), ++val[tot]; int x;
do {
x = stk[top--], ins[x] = 0;
G2.link(x, tot), ++val[tot];
} while (x != v);
}
} else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
}
}
  • 需要注意的是,根节点所在的点双的方点并不会创建,在大多数情况下,这并不会有影响,可根据题目的需要取舍。

性质

由此我们可以发现一些有趣的性质:

  • 现在总点数与原来的点数同阶,现在的总边数与原来的总边数同阶
  • 所有边都是圆点和方点之间的连边,即不存在圆圆边或方方边

多项式学习笔记

持续学习中…

在主席树的基础上做可持久化数组,在可持久化数组的基础上做可持久化并查集。

然而路径压缩的话数组的修改次数可能会很大,但是每次修改是 $O(\log n)$ 的,可能会炸。所以我们要用一种类似启发式合并的方法,把小的往大的合并,这样总的复杂度是 $O(n \log n)$ 的。

可以把并查集中的联通块看成一颗多叉树,合并时,把最深点的深度小的往大的合并,后者把树的大小小的往大的合并。笔者采用的是后者,其实原理基本是一样的。

  1. 单点修改 & 区间查询

    傻逼都会。

  2. 区间修改 & 单点查询

    假设 $a$ 数组为我们当前维护的数组,定义 $b_i = a_i - a_{i - 1}$ ,则 $a_i = \sum_{j = 1}^{i}b_j$ 。用单点修改 & 区间查询的树状数组维护 $b$ ,修改区间 $l$ 到 $r$ 只需使 $b_{l-1} + value$ 且 $b_r - value$ ,查询 $a_i$ 只需求 $\sum_{j = 1}^{i}b_j$ 。

  3. 区间修改 & 区间查询

    同 2 的假设下,求 $\sum_{i=l}^{r} a_i$ 即求 $\sum_{i=1}^{r} a_i - \sum_{i=1}^{l-1} a_i$ ,我们只需考虑如何求 $\sum_{i=1}^{k} a_i$ 。

    $\sum_{i=1}^{k} a_i = \sum_{i=1}^{k} \sum_{j=1}^{i} b_j = \sum_{i=1}^{k} b_i \times (i + 1 - x) = (k+1) \times \sum_{i=1}^{k} b_i + \sum_{i=1}^{k} (i \times b_i)$

    所以我们开两个树状数组,分别维护 $b_i$ 和 $i \times b_i$ 即可。

用 tarjan 遍历整个图,如果某个点是割点,当且仅当以下两种情况

  1. 当前点是根节点,且当前节点出发独立的联通分量至少有两个
  2. 当前点不是根节点,且当前节点出发的独立分量能回溯到的最早的点在当前节点之后

转换过来就是下面两个条件

  1. u == root && child >= 2
  2. u != root && low[v] >= dfn[u]

其他与 tarjan 算法无异。

线性基(洛谷3812)

线性基是一种解决异或相关问题的算法。

感谢 mwh 与我分享关于线性基的理解,让我了解线性基。

概念

线性基理论上来说是一种贪心的思路。一般情况下,我们需要从(二进制)高位到低位贪心,然而这样可能会产生其他影响(例如当前数的选择与否会影响到之前已选择的数)。线性基就巧妙的解决了这个问题。

假设我们已经有了一个集合 $S$ ,集合中有一数为 $P$ ,现在我们需要插入 $X$ ,则插入 $X$ 和插入 $ X xor P $ 是等价的,理性证明:

假设集合 $S$ 中任意个数其中包含 $P$ 的异或和的集合为 $S1$ ,不包含 $P$ 的为 $S2$ 。则插入 $X$ 后的 $S$ 中任意数的异或和集合 $S’ = X xor S1 + X xor S2$ ;插入 $X xor P$ 后 $S$ 中任意数的异或集合 $S’’ = (X xor P) xor S1 + (X xor P) xor S2 = X xor (P xor S1) + X xor (P xor S2) = X xor S2 + X xor S1$ 。所以 $S’ = S’’$ 插入 $X$ 和插入 $X xor P$ 等价,证毕。

主席树(洛谷P3834)

在 mwh 大佬的指引下,我最近学习了主席树。

思想

主席树是一种特殊的线段树,能够存储线段树的历史版本,我们称这种性质叫做可持久化。

主席树的可持久化通过这样来实现:我们每次修改单个节点,必然只会经过 $log_2n​$ 条“线段”,对于这些线段,我们都新开节点来存储。显然对于每一次修改操作,根节点都会被新建。那么我们只要存储下来每一次修改说对应的根节点即可。空间占用 $O(n log n)​$

具体思路可参考 https://www.luogu.org/blog/LonecharmRiver/zhu-xi-shu ss中的图片。

关于模板题

我们要维护静态区间第 k 小。可以先把数组离散化,比如:

1
2
3
离散化前 4 1 1 2 8 9 4 4 3
离散化后 4 1 1 2 5 6 4 4 3
离散数组 1 2 3 4 8 9

我们根据离散数组作为所维护的区间。第 i 棵树存储 [1, i] 内各数值出现的次数。

高斯消元学习笔记

最近的模拟赛出现了一道坑爹的数学题,正解是上一篇博文所讲的数学插值。然而高斯消元还是可以拿到 65 分的成绩,没办法,凭借着我对其原理的依稀记忆我只能考场上手推高斯消元。

原理

高斯消元其实是个很简单的东西,无非就小学奥数的难度罢了。按照小学奥数的加减消元和代入消元即可完成。模板题给了你 n 个的 n 元一次多项式求解。我们可以通过加减消元合并为 n - 1 个 n - 1 元的一次多项式(合并相邻两个);于是,经过 n - 1 次合并我们就可以得到一个一元一次方程,可以很方便的得到解。我们再将解回代,即可解出方程。

给你平面上的 n 个点,可以唯一确定一个多项式。

现在告诉你这些点的坐标和 k ,请你求出多项式在 k 的取值。

思路

显然我们可以根据题意列出 n 个方程,利用高斯消元求解后带入。时间复杂度O(n ^ 3)

我们可以利用插值法求解并使得时间复杂度降至O(n ^ 2)

前言

和 Splay 一样,非旋 Treap (又名 fhq-treap)也是平衡树的一种。由于其不需要进行旋转操作,故可利用其进行可持久化。

写一颗非旋 Treap,我们只需要合并、分离操作,其他的只要有颗脑子就会了啦!

定义

我们定义类FhqTreap为非旋 Treap 主体,结构体node为其节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class FhqTheap {

private:

struct node {
int val, rnd; // val => 该点存储的值,rnd => 该点键值,随机产生
int siz, ch[2]; // siz => 该点包括其子树的节点大小,ch[2] => 指向左/右儿子
} e[maxn];
int tot, root; // tot => 节点总数,root => 根节点
int x, y, z; // 操作过程中的临时变量

// Your Code Goes Here...

public:

// Your Code Goes Here...

} s;

踏上平衡树征程的第一步…

前言

Splay 是一种简单且功能丰富的平衡树结构,其算法核心 Splay 操作能维持其均摊复杂度维持在 $O(logn)$ 。

定义

我们将整棵 Splay 定义在结构体中。

并定义结构体node来表示 Splay 的每一个节点。

宏定义e[0].ch[1]为根节点, $1e9 + 10$ 为INF,并在结构体尾取消定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Splay {
#define root (e[0].ch[1])
#define inf (1e9+10)
struct node {
int val; // 当前节点存储的值
int cnt; // 当前节点存储的值出现的次数
int siz; // 当前节点包括其左右子树中包含的数的个数(不是节点数!)
int father; // 当前节点的父亲节点
int ch[2]; // 当前节点的孩子节点,ch[0]表示左孩子,ch[1]表示右孩子
}
// your code goes here...
#undef root
#undef inf
}

思路

之前我们讲到了用 Splay 写普通平衡树,这次我们将用 Splay 来完成区间操作。

之前的 Splay 是按照权值排序,而这里的 Splay 则是要按照编号排序。

不难想到,整棵树的编号第 k 大点即数列中的第 k 个,整棵树的中序遍历即被维护的数列。


假设我们要翻转区间[l, r],那么我们先把l - 1旋转到根节点,再把r + 1旋转到根节点的右孩子。那么r + 1的左子树即区间[l, r]。翻转该区间只需要把该区间内的每个节点的左右子树交换即可。

参考线段树的 lazytag,我们也使用一个类似于懒标记的方法,保证复杂度为O(log n)

1.png

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
int n, x, f[100001];
int main() {
memset(f, 63, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &x), *std::lower_bound(f + 1, f + n + 1, x) = x;
printf("%d\n", std::lower_bound(f + 1, f + n + 1, f[0]) - f - 1);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×