签到题。
不 FST 就是签到题。
签到题。
签到题。
题目大意：给你 $m$ 个集合，每个集合有若干 $1\sim n$ 的元素，删除某个元素需要耗费一定的代价。删除后，对第 $i$ 个集合中的元素，两两连一条颜色为 $i$ 的边。要求该图中不存在一个环使得环中所有边颜色相同。求最小代价。
题解：将集合编号 $i$ 和其中的元素 $j$ 连边，得到一个二分图。注意到一个环同时也是二分图中的一个环，那么显然需要求二分图的一棵最大生成森林。
题目大意：设有函数 $f: \mathbb{N}\times\mathbb{N}\to\mathbb{N}$。给你一个长度为 $n\le1.5\times10^{4}$ 的数列 $a_{i}=i$，允许进行 $q\le5\times10^{5}$ 次操作，每次操作选择下标 $x,y$，令 $a_{x}:=a_{y}:=f(x,y)$。要求给出一个操作序列，对于任意的 $f$ 均可使得操作完后 $a$ 数组中元素不超过 $2$ 种。
题解：容易发现，使用 FFT 的技巧可使一长度为 $2$ 的幂的数组变得相等，而使用 ST 表的技巧即可使得元素数量不超过 $2$。
题目大意：给你一个完全图，所有边的边权互异。现在将图划分成若干个团，要求每个团内部的边权严格小于它里面的点连到外面的边权。求对每个 $x$，求划分为 $x$ 个团的方案数。
题解：假设一个团的最大边权为 $x$，将所有 $\le x$ 的边连起来，考虑 $x$ 所在的连通块，所有的点必须包含，否则会导致非法。而其它连通块的点则不得包含，否则会导致该连通块的最大边权超过 $x$。那么只要 $x$ 所在的连通块是一个团即合法，而我们的目标是将原图划分成若干个这样的团。这个也比较简单，从小到大加边，如果两个连通块合并，乘一下 dp 数组，如果一个连通块变成了团，那么方案数加 1。
题目大意：给出 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$，要求你找出 $m$ 个三元组 $\{(u_{i},v_{i},w_{i})\}$，使得 $a_{u_{i}}=a_{w_{i}}=0$，$a_{v_{i}}>0$，$u_{i}<v_{i}<w_{i}$，所有 $a_{v_{i}}$ 互异，所有 $u_{i},v_{i},w_{i}$ 互异。求 $m$ 的最大值。
题解：将所有非零的数分为左部 $L$ 和右部 $R$，其中 $L$ 中的数是那些左侧 $0$ 比右侧 $0$ 少的数，反之亦然。注意到，对于所有 $L$ 中的点，不论左侧怎么匹配，它都能找到一个右侧的点来匹配，反之亦然。下文称非零的 $a_{i}$ 值为颜色。对于同种颜色且同在 $L$ 中的点，设 $u_{1}<u_{2}$，那么假如 $u_{1}$ 能匹配，$u_{2}$ 也能匹配。也就是说，对于同种颜色，我们只需要保留 $L$ 中最右的点及 $R$ 中最左的点，且对 $L$ 中的点，我们只关心能否在它左侧找一个点匹配，$R$ 同理。那么我们把所有颜色看做左部，所有 $0$ 看做右部，每个左部的点连向了右部的一段前缀和一段后缀。注意这个图很特殊，我们将右部的 $L$ 和 $R$ 交换，可以发现所有的前缀和后缀就拼在一起变成了一个区间，而这种二分图是很容易贪心求最大匹配的。最后求得的答案可能大于 $\frac{\text{cnt}_{0}}{2}$，需要注意特判。
题目大意：给你 $n$ 个互异整数，它们都在 $k\sim2^{c}-1$ 之间。现在进行 $k$ 次操作，每次等概率随机将其中一个数减 $1$。求期望异或值。$1\le k,c\le 16$。
题解：朴素的想法是直接 dp。$dp[i][j]$ 表示异或和为 $i$，已经减了 $j$ 次的方案数。但是复杂度是 $2^{2c}k^{2}$。注意到 $k$ 很小，因而大部分的数在减的时候只会影响低几位，而不会影响高位。具体来说，只影响低 $i$ 位的数大约有 $2^{c-i+\log k}$ 个。
考虑在线段树上 dp，设某个节点代表的区间为 $[l,r]$，我们只考虑那些在 $[l+k,r]$ 中的数，这样所有的数即使减了 $k$，前缀一定还是 $l\land r$。考虑合并两个结点的时候如何合并 dp 数组。对于右孩子的 dp，若它已经处理的数有奇数个，那么 dp 数组的 $i$ 需要整体加一个前缀 $1$。合并时则可简单地把 dp 数组视为集合幂级数，用 FWT 处理。注意到还需要加入 $[r,r+k-1]$ 中的数，这些都可以分别用 FWT 处理。
合并左右子树的复杂度为 $\sum_{i=0}^{c-1}2^{i}\cdot k^{2}\cdot 2^{c-i}=2^{c}ck^{2}$，加入新数的复杂度为 $\sum_{i=0}^{c-1}2^{c-i+\log k}\cdot 2^{i}\cdot k^{2}=2^{c}ck^{3}$。因而总复杂度为 $\mathcal{O}(2^{c}ck^{3})$。