通常的染色问题是NPC问题，但此题多了m−n<=5的限制，可以将图的大小缩小来解决。将问题拓展为：每条边有两个权值，分别表示两个点同色、不同色时的权值，而一张图染色后的权值就是每条边的权值之积。这样对应原问题时，每条边同色时的权值为0，异色时的权值为1。拓展后的问题可以进行“消点”操作，具体如下：

  • 度数为1的点可以直接删除，并在最终的答案上乘上k−1.

  • 对于度数为2的点，设这个点连向a和b，则可以删除这个点并在a和b之间连一条边，讨论这个点的颜色来决定这个点的权值。具体如下:

    – 如果a和b同色，则有一种情况是这个点与a与b均同色，k−1种情况是这个点与a与b均不同色；

    – 如果a和b不同色，则有k−2种情况是这个点与a与b均不同色，一种情况与a同色，一种情况与b同色。

根据以上规则即可算出新连的边的权值，使得新图与原图等价。

  新图中不会包含度数小于等于2的点，因此新图中的点数n与边数m满足3n≤2m，又因为m−n≤5，所以n≤10且m≤15.

  随后用状态压缩dp进行子集转移即可在O(nm3^n) 的时间内求出新图的权值。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19494007

大意

给你一个矩阵的黑白情况，求是否能通过交换行和列达到主对角线上全是黑点。

思路

我们考虑从这个点的行向列连边，跑二分图匹配。

原因在于，我们如果交换两行或者两列，无非是交换了连边，最终的匹配不会发生改变。

于是只需要二分图匹配一下，看看是否能刚刚好匹配出来即可。

更好的阅读体验:https://www.cnblogs.com/To-Carpe-Diem/p/19434503

大意

给出一段区间的颜色，区间询问，求某段区间两个点颜色相同的概率(用分数表示)

思路

发现询问和查询隔离，考虑莫队。

然后我们的修改是不是只需要考虑多一个或者少一个点，那么这个很好办啊。

如果记当前答案(分子)是 $\text{ans}$，则在加入点的时候，$\text{ans}$ 先加上原来这个新加入点颜色的贡献，如果是删点的花就先把删掉的这个点的贡献减去，$\text{ans}$ 的贡献就减去减掉后的这个贡献。

然后注意 long long 即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19434487

大意

在 $i$ 的地方会向后跳 $a[i]$ 次，然后带修询问你最少需要跳几次能跳出这个长度为 $n$ 的地方

思路

首先我们发现每个点的弹出，会影响下一个点 $i + a[i]$，也就是说我们如果暴力的考虑的话，就只需修改的时候向后一直跳。

但是这样很劣啊，我们可以考虑用分块处理这个问题，我们可以考虑倒序处理，当后面的点处理过后，你就可以把前面的点从后面转移。

于是我们只需要记录 $cnt[i]$ 次才能跳出第 $i$ 块，以及 $nxt[i]$ 弹出块后落到的第一个位置。

那么我们就可以分块直接处理这个玩意，当一个点被修改的时候，只会影响这个点所在的块，直接重新对这个块建一遍即可。

这个题最开始叫根号序列的，因为这个题的三个算法分别是分块，根号分治和根号重构。

$cnt(k)$ 显然是好求的，只需要解决 $\sum [f_i=k]a_i$ 即可。

注意到 $a_i$ 是区间加的，但 $f_i$ 是单点改的，所以可以得到一个 $O(n\sqrt{n})$ 的分块做法。

维护 $s_{i,j},b_{i,j}$ 表示第 $i$ 块中数字 $j$ 的 $a_x$ 之和/个数，对于区间加，散块暴力修改 $a_i$，整块维护每个块的懒标记值 $t_i$，复杂度 $O(\sqrt{n})$。

对于区间询问 $k$，则第 $x$ 块对答案的贡献是 $s_{x,k}+b_{x,k}\times t_x$。复杂度 $O(\sqrt{n})$。

单点修改 $f$ 只需要暴力更改即可，复杂度 $O(1)$，这个过程只要维护好 $b,s$ 两个数组就行。

不难发现这个做法的空间复杂度为 $O(n\sqrt{n})$，但空间限制是 32 MB。考虑优化。

不难发现瓶颈在于 $b,s$，我们对每种数字都记录了 $\sqrt{n}$ 个信息，实际上，这种方法只适用于元素 $f_i$ 出现次数很多的情况，但若一种元素 $f_i$ 出现次数很少，直接暴力遍历也可以解决，考虑阈值分治。

先不考虑修改了 $f_i$ 的情况。若 $cnt(x)\ge \sqrt{n}$，则我们维护元素 $x$ 在 $\sqrt{n}$ 块的信息，反之用 vector 或链表维护元素 $x$ 在序列中的位置。

前者元素种类数不超过 $\sqrt{n}$，所以空间是 $O(n)$，后者显然是 $O(n)$。时间上，传统的分块做法单次查询 $O(\sqrt{n})$，而后者元素的出现次数不超过 $\sqrt{n}$，时间也是 $O(\sqrt{n})$。

考虑加入修改 $f_i$ 的操作，不难发现可能存在元素从 $cnt(x)$ 从 $\ge \sqrt{n}$ 变成 $< \sqrt{n}$。考虑定期重构，对操作分块，每 $\sqrt{n}$ 次操作就重新根号分治做初始化。

对于修改了 $f_i$ 的位置 $i$，在下一次重构前，我们不用分块也不用 vector 维护，而是把他们专门放到一个 vector 里，统计他们对每个询问的贡献，因为定期重构，这个 vector 内元素个数不超过 $\sqrt{n}$。

这一部分要注意把修改了 $f_i$ 的位置 $i$ 从原数据结构中删除，分块的直接删掉贡献，vector 可以用懒惰删除，最后总复杂度就是 $O(n\sqrt n)$。