【切割】题解

sevenki · 2024-01-21 09:40:33 · 题解

tag: 随机赋权、线性基（不是必须的）

大概是比较有意思的题目。

但是，这是一道原题。Luogu P5227

这道题的难点主要在于：

• 想到随机赋权。
• 知道怎么赋权。

在赛场上原题面的数据范围下，这道题读入估计得花 1 个月。

后来出题人把 c 的数据范围改成和原题一模一样。

思路

下面说本题做法。

随机赋权，使删去一些边，使得图刚好不联通的边集的权值异或值为 0。

“刚好不联通” 指的是，少删任意一条都能连。

怎么办呢？

我们考虑几个简单情况。

对于一个点，把所有和他相关的边切掉，图就不联通了。因此，一个点的所有连边的异或值为 0。

如果按照这个方法赋权，那么：

对于一个联通的点集，与外界（两点非联向该点集的边）的边权异或值将会是什么？

每个点连的边的异或值为 0。点集里，每个点都按照这样算一次，异或值显然为 0。

此时，联向外面的边由于一端联向点集中，因此被计算 1 次。 联向里面的边由于 2 端联向点集中，因此被计算 2 次，直接就抵消了。

那么结果其实就是联向外面的边权异或值。而结果为 0。

于是，只要能构造出“一个点的所有连边的异或值为 0” 的图，问题就解决了。

构造方法：

随便来一棵生成树。

对于图中不在树上的边，随机赋权。

父亲联向孩子的边，就是孩子的除了联向父亲之外其余边的异或和。

这样子就能保证每个点的所有连边的异或值为 0。

由于权值随机，所以不符合条件，异或值却恰恰为 0 的概率比较小。这样子我们就从概率上解决了这个问题。

注意，出错的概率随着 c_i 增大而增大。这个问题在后面会有细致的说明。

解决询问

对于每次询问，如果其中任意几条边的异或和为 0，那么把它们删掉图就不联通。

如果暴力枚举边集，复杂度就会达到 2^c。然而，在 c\leq 4 的情况下，暴力枚举的方法跑的飞快。

如何才能去掉这个指数，使得 c 的范围可以更大？

我们可以考虑线性基。

用线性基可以在 O(c \log w) 的时间内判断几个数中是否有异或和为 0 的组合。

线性基可以动态插入，也可以高斯消元。前者容易写得多。

这样子，我们就可以在时间上通过 \sum c \log w 的数据。不保证正确性。 我的意思是，在 c 大的情况下，正确性几乎为 0\%。

关于概率

为什么我们的随机算法不能通过 c 很大的数据？

先看线性基的重要性质：

• 线性基中没有异或和为 0 的子集。
• 线性基中各数二进制最高位不同。

显然，如果前面的几个数构造的线性基把 64 个位置占满了，那么后面的数就不会再增加新的线性基元素。

如果没有插入到任何一个位置上，则表明该数可以由线性基中若干个元素的异或和表示出。也就可以用原来的元素异或出。

那么该数与线性基中这若干个元素的异或和为 0。

这样子的话，当 c\ge \log w，无论删的是什么边都可以使得异或和都为 0。

那么我们的概率正确就被打破了。

比如，有一个环。i\to i+1\bmod n。

在这里面随便多连几条边。

我们询问把这多连的边删掉图连不联通，答案显然为 1。

但是如果询问的边数量大的话，则可以使得异或和为 0 了。

而我们定义异或和为 0 表示删掉这几条边图不联通。显然发生了矛盾。

所以这就是上述问题的 ans。

另外，还有一个很重要的性质：