题解：P12521 [Aboi Round 1] ATRI

cike_bilibili · 2025-05-19 11:37:19 · 题解

前言

上语文课的时候想到的 idea。

好像被爆标了，但是因为时限 5s 和正解 \mathcal{O}(\frac{n^2}{\omega}) 的复杂度还是评了蓝。

合并果子的异或版本，输出所有可能值。

爆搜，随便怎么搜都行。

从这里开始就要推性质了。

首先我们知道一个数被异或了偶数次就会变成 0，只有异或奇数次才会参与贡献计算，所以我们考虑会有哪些点留下。

我们将合并的过程化成二叉树的性质，具体的，是一棵有 n 个叶子，n-1 个非叶子节点的二叉树，每一个非叶子节点都对应了一次合并，那么会产生贡献的就是那些深度为偶数的点。

现在直接给出结论，在所有情况中最后参与贡献的可能点数在模 3 意义下同余。

考虑数学归纳，在 n \le 5 时都成立。

假设 n 情况成立，考虑 n+1，实际就是把一个叶子节点分裂成两个，如果这个点是偶深度节点，那么分裂就会失去一个偶深度节点，否则多产生两个偶深度节点，所有数要么 -1，要么 +2，最后一定在模 3 意义下同余。

于是搜索选哪些点就行了。

记录 f_{i,j,k} 表示前 i 个数选了 j 个，异或值为 k 是否可行，O(n^2 V) 大力转移即可。

有两个优化思路，一个是压位，一个是优化状态。

先讲状态，我们可以将 i 这一位滚动掉，j 这一位记录选的个数模 3 的值，时间复杂度变为 O(nV)。

压位也很简单，将 k 这一位每 64 位分个块，全局下标异或可以转化为块间交换，块内位运算解决，全局或也很好实现。

使用一个优化可以通过 Subtask 4，全部使用可以通过此题。