省选 D2T2，但是……

· · 题解

starmap 题目链接

怎么大部分做法都是对着图结构构造，我好像根本想不到/kk

记一下我的汤柿做法。/kel

刻画操作

自然的想法是在邻接矩阵上刻画 k-完全子图 边的翻转，但这样的操作即为选出 k 行以及编号相同的 k 列，把它们构成的子矩阵异或 1，这并不好继续做下去。

不妨把邻接矩阵展开成一个 \dbinom{n}{2} 维向量，那么本题做的事情就是从 \dbinom{n}{k} 个向量张成的线性空间中找出与初始边集异或后 \operatorname{popcount} 最大的向量。

可以自然地想到求这些向量的线性基，进而分析操作的性质。

找线性基中的规律

首先要找到构建线性基的方法。

由于空间只有不超过 \dbinom{n}{2} 维，尝试不断随机加入操作。实验发现 O(n^2) 轮后线性基就不再变化。

这样得到的线性基比较杂乱，考虑消元成最简形式。

尝试输入不同的 n,k 可以观察到以下四类线性基：

(n=9,k=4)

(n=9,k=5)

(n=9,k=6)

(n=9,k=7)

可以观察到：固定 k 改变 n，线性基的结构不发生变化；固定 n 改变 k，线性基的形态只与 k\bmod 4 有关。

第一问

第一问的答案即为拿初始的边向量异或上线性基中部分向量得到的最大的 \operatorname{popcount}。

根据观察到的线性基形态，可以对不同的 k\bmod 4 设计不同的办法求解答案。

k \bmod 2=0

此时线性基的形态非常简单，只需要模拟或讨论就能得到答案。

k\bmod 4=3

此时线性基的秩 r=\dbinom{n}{2}-n+1。

对于前 r 行，后 \dbinom{n-1}{2} 列恰好有 2 个 1，且这些 1 的位置取遍 \dbinom{n-1}{2} 种可能。

考虑把初始的边向量异或其前 r 项中为 0 的项对应的行，得到前 r 项均为 1 的向量。

这时候再施加一个操作会让后 n-1 项中的两个位置和对应的一个前 r 项的位置发生翻转。为了让 \operatorname{popcount} 增大，这两个位置必须全是 0。

因此设后 n-1 项有 c 个 0，\operatorname{popcount} 能增加 \lfloor\dfrac{c}{2}\rfloor。模拟即可。

k\bmod 4=1

这时线性基看上去比较复杂，但是还是不难分析出它的结构。

其秩 r=\dbinom{n}{2}-n=\dbinom{n-3}{2}+2(n-3)，倒数第 n 列全是 1，最后一列只有靠后的 n-3 行不是 1，倒数第二列只有中间 n-3 行不是 1。前 \dbinom{n-3}{2} 行的倒数第 n-1 至倒数第 3 列每列恰好 2 个 1，取遍 \dbinom{n-3}{2} 种可能。接下来 n-3 行的这些列每行恰有 1 个 1，取遍 n-3 种可能。再接下来 n-3 行类似。

仿照 k\bmod 4=3 的情况，依旧是把初始的边向量操作成前 r 项全 1。

先来考虑用前 \dbinom{n-3}{2} 行的操作进一步增大 \operatorname{popcount}。

此时如果不改变倒数第 1,2,n 项，只能再做偶数次操作，设那 n-3 项中有 c 个 0，就能把 \operatorname{popcount} 增大 2\times \lfloor\dfrac{c}{4}\rfloor。

如果剩下不少于 2 个 0，还可以再做一步，但不一定能把答案变大，做一些讨论即可。

问题是还有 2(n-3) 行的操作可以做，某些情况下也确实需要用它们来增大答案。如果要考虑这些行可能会增大很多讨论难度。

但经测试发现：给图的点标号随机打乱，跑 O(1) 轮，只使用前 \dbinom{n-3}{2} 行就能得到正确答案！

我不懂这里的道理，但是它似乎是对的qwq

以上的信息都能使用很低的复杂度计算（不必显式建出线性基），至此就解决了第一问。

暴力构造

求答案的方法直接给出了需要异或的向量有哪些，因此找到线性无关的 r 个操作就能生成线性基。直接模拟可以得到步数不超过 \dbinom{n}{2} 的构造。但是构建线性基时间复杂度为 O(\dfrac{n^6}{\omega})。

构造的框架

此前的尝试已经指导了构造的流程：通过模拟求答案得到需要线性基的那些行，然后把这些行对映到原题的操作。

自然地去尝试直接得到线性基每一行对应的原题操作。可以发现一些行能用 O(1) 个操作造出来，而另一部分似乎不能简单地造出来。尝试观察每一行的图结构是什么。

k\bmod 4=0

此时的线性基每一行对应两条边。（其中一条是 1-2）

k\bmod 4=1

此时的线性基前 \dbinom{n-3}{2} 行每一行对应如下结构：

后面的 n-3 行每行对应如下结构：

再后面 n-3 行每行对应如下结构：

k\bmod 4=2

此时的线性基每一行对应一条边。

k\bmod 4=3

此时的线性基每行对应一个三元环（其中一个点是 1）。

构造小结构

上面的结构当然不能每个都简单造出来，因此尝试组合出来它们。

四元环可以通过打表或手玩得到任意 k 的 4 步构造。

又发现下图结构可以拆成两个四元环：

因此直接解决了 k\bmod 4=1 时的问题。

当 k\bmod 4=3 时，一个简单的想法是把 含 1 三元环 两个两个一组使用上面的结构生成，但有可能最后剩一个。

回到求答案的过程，可以观察到三元环数量和初始的边数 m 奇偶性有关，而原题的一步操作恰好能翻转图上边数的奇偶性！这样开始时随便做一次操作就解决了这种情况。

接下来还剩 k 是偶数。

类似 k\bmod 4=1 与 k\bmod 4=3 的关系，只需要解决 k\bmod 4=0 就能解决 k\bmod 4=2。

但造两条边还是比较困难的。发现两条边可以由两个以下结构拼出，这个结构的好处是只考虑三个点：

打表发现这个结构可以 2k-2 步生成。

至此已经能得到 O(n^2k) 步的构造了，这太大了。

注意到可以先用异或四元环的方法把要造的边数缩减到 O(n)（就是每次拿四元环异或一个四个点的链），这样总操作步数就是 O(n^2) 的了。

有趣的是，对操作记忆化，上面的构造写出来似乎都不会超过 \dbinom{n}{2} 步。大概能分析出来这个上界，不过我还没有尝试 qwq

这样做可以规避大部分线性代数的推导和手玩构造，但代价是似乎根本没做明白这道题/xk

而且实现过程中确实要讨论很多东西，赛时大概很难做到如此解决这道题。