专栏文章

题解：AT_abc390_d [ABC390D] Stone XOR

封封禁用户
AT_abc390_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqd43mx
此快照首次捕获于
2025/12/04 02:50
3 个月前
此快照最后确认于
2025/12/04 02:50
3 个月前
查看原文

题目传送门

atcoder
洛谷

拿到一道题，首先思考：

题目是说有 NN 个袋子，每个袋子里有若干石头。我们可以进行任意次数的操作，每次选两个袋子 AA 和 BB，把 AA 的所有石头移动到 BB 里。最后，每个袋子的石头数 BiB_i 的异或和有多少种不同的可能值。输出这个数量。
首先，我得理解操作的结果。每次操作可以合并两个袋子，比如把 AA 的石头全给 BB。经过多次操作后，最终的袋子分布其实是把原来的袋子分成了若干个组，每个组的石头总和被分配到某个袋子中。比如，假设最后剩下 kk 个袋子，那么每个袋子里的石头总和是原来某些袋子的总和。比如，最初的每个袋子 ii 的石头总和会被合并到某个最终的袋子里。
那这个时候，问题可以转化为，如何将所有袋子分成若干个非空的不相交的组，每个组的和作为该组的贡献，然后将这些组的数值异或起来。不同的分组方式会得到不同的异或和。我们需要找出所有可能的分组方式对应的异或值的不同数量。
那问题就转化为，枚举所有可能的分组方式，计算它们的异或和，然后统计不同的值的数量。
但怎么枚举所有可能的分组呢？比如，当 N=3N=3 的时候，分组可以是三个单独的，或者两个合并成一个，或者全部合并成一个。不同的分组方式对应不同的异或结果。
那这个时候，每个分组方式可以看作是将原数组 AA 划分成一个集合的子集，每个子集至少有一个元素，且所有子集的并集是全集。每个子集的和作为异或的一个元素。然后，这些子集的和异或的结果就是最终的值。
但是，这样的划分方式可能有多种，比如不同的划分结构。比如，当 N=3N=3 时，可能的划分结构包括：三个单独的分组，两个分组（比如袋子 11 和 22 合并，袋子 33 单独），或者一个分组。不同的结构对应不同的异或结果。
那这个时候，问题就转化为，如何枚举所有可能的子集划分，然后计算每个划分对应的异或总和，最后统计不同结果的数量。
但这样的枚举方式在 N=12N=12 的时候会不会很困难呢？因为 NN 是 1212，可能的划分数是贝尔数，贝尔数的第十二项是 42135974213597，这在千万级别。那对于每个划分，我们需要计算异或总和，然后将这些总和存入集合中，最后统计数量。这似乎对于 N=12N=12 来说，贝尔数可能超过 10810^8 的话，可能会有问题，比如时间不够或者内存不足。但是看样例中的第三个测试样例输出是 8484 ，可能实际可行的分组方式并没有那么多？
或者，可能题目中的某些性质可以减少计算量。比如，异或的性质可能允许某些不同的分组方式得到相同的异或结果，因此不需要枚举所有可能的划分，而是可以找到一种更高效的方式。
那回到代码（见下）。它用了深度优先搜索的方式，对于每个袋子，选择它属于哪个组。比如，optopt 数组记录每个袋子被分配到哪个组。例如，opt[i]=kopt[i] = k 表示第 ii 个袋子被分配到第 kk 个组。这里的组是按顺序编号的，比如第一个袋子必须分到组 11，第二个袋子可以分到组 11 或者组 22，第三个袋子可以分到已有的组或者新组，等等。这样，不同的 optopt 数组的排列对应不同的分组方式，但可能会有重复的情况。比如，组编号的排列顺序不影响分组的实际结构，比如组 11 和组 22 的顺序调换，但分组方式相同的话，它们的异或结果是一样的。所以，这样的枚举方式可能会导致重复计算吗？
比如，假设两个分组方式的结构是相同的，只是组的编号不同，那么它们的异或结果可能相同。例如，假设袋子 11 和袋子 22 被分到组 11，袋子 33 被分到组 22，或者袋子 11 分到组 22，袋子 22 分到组 22，袋子 33 分到组 11。这种情况下，它们的异或和会是相同的，因为异或的顺序不影响结果。因此，这样的不同 optopt 数组对应的分组方式会被视为不同的情况，但实际它们的异或结果相同。那么，在代码中，如何处理这种情况？
看代码中的 dfsdfs 函数，optopt 数组存储每个袋子被分配到的组号，比如，对于 n=3n=3 的情况，可能的 optopt 数组可能是 [1,1,2][1,1,2]，或者 [1,2,1][1,2,1]，这会被视为不同的分组方式吗？是的。但是，在计算异或的时候，组的顺序不影响异或的结果，因为异或是交换的。所以，这两种不同的 optopt 数组对应的异或和是一样的。那么，这样就会导致在 ansans 数组中存入重复的值，最终通过排序去重来得到正确的数量。
所以，这个算法的思路是枚举所有可能的组分配方式，不管组的顺序如何，然后将它们的异或和存入数组，最后去重统计数量。因为不同的组分配方式可能生成相同的异或结果，所以通过 uniqueunique 处理后的结果就是正确的答案数量。
那这个算法的时间复杂度如何？比如，对于每个袋子 ii，选择它所在的组的编号。而组的编号不能超过当前的最大值加一。例如，第一个袋子必须分到组 11。第二个袋子可以分到组 11 或组 22。第三个袋子可以分到组 11、组 22 或组 33，或者如果前面的组的最大是 22，那么可以分到现有的或者新增的组 33。这样，这种枚举方式实际上生成了所有可能的非空划分，其中组的顺序被考虑，但异或的顺序不影响结果。
所以，这样的枚举方式会产生很多重复的分组结构，即不同组的顺序会被视为不同的情况，但它们的异或结果可能相同。所以，这样的枚举方式虽然会生成很多重复的异或结果，但最终通过 uniqueunique 去重，得到正确的答案。
例如，对于 n=3n=3 的情况，不同的分组方式的数量等于贝尔数，也就是 55 种可能的分组方式。但通过这种枚举方式，可能生成的 optopt 数组的数量比贝尔数大。例如，贝尔数是 55，而该算法枚举的可能更多？
比如，n=3n=3 时，分组方式的数量是 55 种。但是根据这种枚举方式，每个分组方式对应的组编号可能不同。例如，对于分组方式 {{1},{2},{3}}\left \{ \left \{ 1 \right \} ,\left \{ 2 \right \} ,\left \{ 3 \right \} \right \} ，对应的组编号可以是 11、22、33，或者其他排列吗？
比如，假设第一个袋子分配到组 11，第二个袋子可以选择组 11 或组 22。假设选择组 22，第三个袋子可以选择组 11、组 22 或组 33。如果选择组 33，那么分组是三个单独的。或者，对于第三个袋子，如果第二个袋子分配到组 22，第三个袋子可以选择组 22 的话，那么分组是 {1}\left \{ 1\right \} ，{2,3}\left \{ 2,3 \right \} 。或者，如果第三个袋子分配到组 11，那么分组是 {1,3}\left \{ 1,3\right \} ，{2}\left \{ 2\right \} 。所以，这种方式枚举的是所有可能的组分配，其中组的编号是按顺序分配的。因此，这种方式确实枚举了所有可能的分组结构，不管组的顺序如何。例如，对于分组结构是合并袋子 11 和袋子 22 的情况，对应的组编号可能是组 1、1、21、1、2（如果第三个袋子分配到组 22），或者组 1、1、31、1、3（如果第三个袋子分配到新的组 33），但异或的结果是相同的，因为组的顺序不影响异或的结果。因此，不同的 optopt 数组可能生成相同的异或和，但通过最终的 uniqueunique 处理，得到正确的结果。
因此，这个算法的正确性基于：枚举所有可能的分组方式的异或和，然后去重得到不同的值。虽然枚举的方式可能产生不同的 optopt 数组，但它们对应的异或和可能相同，但最终会被 uniqueunique 处理掉，所以结果正确。
那这个算法的时间复杂度如何？例如，当 n=12n=12 时， optopt 的可能情况有多少种？这应该等于递推的贝尔数吗？或者可能更高？
这里，每个袋子 ii 的选择是：可以分配到前面的任何一个已经存在的组（组的编号不超过当前的最大值），或者创建一个新的组（当前最大值 +1+1）。例如，对于第 ii 个袋子，它可选的组的数量等于当前的最大组数 +1+1。而每次选择的时候，maxnmaxn 是当前的最大组号。例如，当处理到第 ii 个袋子时，假设前 i−1i-1 个袋子的组分配的最大组号是 kk，那么第 ii 个袋子可以选择 11 到 k+1k+1 中的任意一个。
这种递归的方式生成的 optopt 数组的数量等于增长数（或者叫做 FubiniFubini 数，或者排列的贝尔数）。例如，对于 n=3n=3，这等于 1313 种可能的分配方式。例如，这个数比贝尔数大，因为贝尔数是 55 种分组方式，而这里可能生成的分配方式数目更大，因为不同的组的顺序被视为不同的情况。例如，在分组结构相同的情况下，不同的组顺序会被视为不同的分配方式，从而导致不同的 optopt 数组，但异或结果相同。
例如，n=3n=3 时，该算法枚举的分组方式数目等于 1313。而贝尔数是 55。这说明该算法生成的 optopt 数组数目大于等于贝尔数，但每个分组结构对应多个 optopt 数组，所以最终生成的异或结果数目可能等于正确的数目，因为不同的结构可能得到不同的结果，但同一结构的不同排列方式可能得到相同的结果，从而被去重处理。
所以，当 n=12n=12 时，这个算法的复杂度可能很高。比如，FubiniFubini 数是随着 nn 的增大而指数级增长的。比如，当 n=12n=12 时，FubiniFubini 数是 4213597×...4213597 × ...？或者可能更高？比如，根据维基百科，FubiniFubini 数（有序贝尔数）的第 1212 项是 4213597×...4213597 × ...？或者可能更高？例如，已知 FubiniFubini 数的前几项是 1,3,13,75,541,4683,47293,545835,7087261,102247563,...1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ...。当 n=12n=12 时，这个数可能非常大，比如超过 10810^8？如果是这样的话，这样的算法在 n=12n=12 的时候可能会超时或者超内存。
例如，样例输入 33 的输出是 8484，这说明当 n=6n=6 时，可能的异或结果数目是 8484。这说明，虽然可能的分组方式数目很大，但不同的分组方式可能生成相同的异或结果，所以最终数目可能较低。
但是，根据代码中的 ansans 数组的大小是 2.6×1072.6\times10^7。而 cntcnt 变量在 n=12n=12 的时候可能会超过这个值，导致数组越界或者错误？
比如，在代码中，MAXNMAXN 是 2.6×1072.6\times10^7。如果当 n=12n=12 时，FubiniFubini 数是约 4×1084\times10^8，显然这会超过 MAXNMAXN 的大小，导致数组溢出。这说明，这个代码可能在较大的测试用例中无法通过，比如 n=12n=12 时会导致 ansans 数组溢出，或者导致运行时间过长。
但是，观察样例输入 22 的输出是 22。这说明，当两个袋子的时候，可能的异或结果数目是 22。而根据分组方式，可能只有两种可能：两个袋子各自单独，异或和为 A1⊕A2A_1 \oplus A_2；或者两个袋子合并，异或和为 A1+A2A_1 + A_2。所以，当两个袋子时，可能的异或结果数目是 22。这说明，该代码在 n=2n=2 时是正确的。
这说明，该代码可能在测试用例的约束下是正确的，但可能对于 n=12n=12 的情况无法处理。然而，在题目给出的约束中，n≤12n≤12，且代码的 ansans 数组的大小是 2.6×1072.6\times10^7，那么这可能意味着在某些情况下，例如 n=12n=12 时，代码无法处理，但可能实际运行通过了？或者可能存在其他优化？
或者，可能问题的实际可行解数目较小，所以虽然分组方式数目很大，但不同的方式可能生成相同的异或结果，导致 ansans 数组中的实际数目不超过 MAXNMAXN 的限制。例如，当 n=12n=12 时，可能不同的分组方式的异或结果数目在 2.6×1072.6\times10^7 以内，所以不会溢出。
或者，可能该代码在 n=12n=12 时，实际上生成的 ansans 数组的大小不会超过 MAXNMAXN 的限制。比如，当 n=12n=12 时，FubiniFubini 数是 42135974213597，这大约是四百万，而每个分组方式的异或结果可能有很多重复，所以 ansans 数组的数目可能远小于这个数值。例如，当每个分组方式的异或结果都是唯一的，那么当 n=12n=12 时，ansans 数组需要存储四百万个数，而 MAXNMAXN 是 2.6×1072.6\times10^7，足够容纳。这样，代码是正确的。
那现在，我们需要理解这个代码的具体实现。代码中的 dfsdfs 函数是递归的，每次处理一个袋子，选择其所属的组号。optopt 数组保存每个袋子所属的组号。例如，opt[i]opt[i] 的值是袋子 ii 被分到的组的编号。当递归到第 tmptmp 个袋子时，maxnmaxn 是目前最大的组号。
例如，当处理到第 tmp+1tmp+1 个袋子时，可以选择将其分配到现有的任何一个组（11 到 maxnmaxn），或者创建一个新的组（maxn+1maxn+1）。然后递归下去。这样，所有可能的组分配方式都被枚举，其中组的顺序是无关的，但不同的分配方式可能生成相同的分组结构，只是组的顺序不同。
当处理到 nn 个袋子后，optopt 数组中的所有元素都被确定。此时，代码中的 bb 数组保存每个组的石头总和。例如，bb 数组的下标是组号，对应的值是所有分配到该组的袋子的石头总和。然后，将这些组的异或和计算出来，存入 ansans 数组中。
例如，假设袋子 11 和袋子 22 被分配到组 11，袋子 33 被分配到组 22，那么 b[1]=a[1]+a[2]b[1] = a[1] + a[2] ，b[2]=a[3]b[2] = a[3]。异或和是 b[1]b[2]b[1] ^ b[2]。而如果袋子 11 和袋子 22 被分配到组 22，袋子 33 被分配到组 11，那么 b[2]=a1+a2b[2] = a_1+a_2，b[1]=a3b[1] = a_3，异或和还是相同的。所以，这样的不同分配方式会被视为不同的情况，但它们的异或和相同，因此在 ansans 数组中会被存入相同的数值，最后通过 uniqueunique 处理得到正确的数目。
因此，这个算法的正确性是正确的，因为它枚举了所有可能的组分配方式，然后计算异或和，并通过去重得到数目。但问题是，当 n=12n=12 时，这样的枚举是否可行？
比如，对于 n=12n=12，每个袋子有多个选择，每个选择生成不同的路径。但这样的递归深度是 1212 层，对于每个袋子来说，选择的组数目可能很大。例如，第一个袋子只能选组 11。第二个袋子可以选组 11 或组 22。第三个袋子可以选组 11、组 22 或组 33，依此类推。假设每个袋子最多有 kk 组的选择，那么总的时间复杂度可能是 O(n!)O(n!)，但实际上可能更高，比如 O(nn)O(n^n)，这在 n=12n=12 时是很大的数值。例如，n=12n=12 时，这样的枚举次数可能高达 12!12!，或者更高。这显然会导致超时。
那为什么这个代码能通过呢？比如，可能题目中的测试用例没有 n=12n=12 的情况，或者该算法的时间复杂度实际上在 n=12n=12 时是可行的？
或者，可能这个问题的正确解法并不是通过枚举所有分组方式，而是利用了异或的某些性质，从而可以快速计算可能的结果数目。比如，将问题转化为线性基的问题，或者通过动态规划的方式。
但是，当前的代码显然是通过枚举所有分组方式，并统计异或结果的数目。这可能适用于 nn 较小的场合，比如 n=12n=12 时，可能实际的运行时间在可接受的范围内？
或者，可能该代码的时间复杂度在 n=12n=12 时是可行的，因为每组选择的方式数可能被优化。例如，当 n=12n=12 时，每个袋子 ii 的选择可能最多有 ii 种组的可能性，那么总的选择次数是 1×2×3×...×12=12!=4790016001×2×3×...×12= 12! = 479001600，这大约是 5×1085\times10^8 次，显然超过时间限制。但代码中的 MAXNMAXN 是 2.6×1072.6\times10^7，而 ansans 数组的大小是 2.6×1072.6\times10^7，可能无法存储这么大的数目。这显然存在矛盾。
那这代码是否真的能处理 n=12n=12 的情况？
可能，这个问题的正确解法是基于分组方式的异或和的性质，允许通过某种数学方式快速计算可能的结果数目，而不是枚举所有可能的分组方式。例如，每个分组的异或和可以看作是某些线性基的组合，从而可以用动态规划来跟踪可能的异或结果。
但代码中的做法显然不是这样，而是直接枚举所有分组方式，这在 n=12n=12 时可能不可行。所以，这说明该代码可能仅在 nn 较小的情况下通过，而无法处理 n=12n=12 的情况，但题目中的测试用例可能没有达到 n=12n=12 的极限情况？
或者，可能这个问题的正确解法确实是枚举所有分组方式，但通过某种剪枝或优化，使得在 n=12n=12 时也能快速处理？
例如，可能，虽然分组方式的数量是贝尔数的量级，但当 n=12n=12 时，贝尔数大约是 4×1064\times10^6，这可能在时间允许的范围内？比如，贝尔数 B(12)B(12) 是 42135974213597，所以当 n=12n=12 时，代码中的 dfsdfs 函数会被调用约 4×1064\times10^6 次。每次调用会处理到 nn 层，当 n=12n=12 时，总的操作次数是大约 4e64e6 次，这可以处理的。例如，每个递归调用的操作是 O(n)O(n) 时间吗？比如，在递归到 tmptmp 层时，循环次数取决于 maxnmaxn 的当前值。例如，对于每个袋子 ii，循环次数是 maxn+1maxn+1，其中 maxnmaxn 是之前的组数。这可能平均下来每个递归调用的循环次数是较小的。例如，当 i=12i=12 时，每个递归调用的循环次数可能平均为 log(n)log(n) 次。这样，总的操作次数可能在合理的时间范围内。
或者，可能这个代码的时间复杂度是 O(Bell(n)×n)O(Bell(n) × n)，其中 Bell(n)Bell(n) 是贝尔数。当 n=12n=12 时， Bell(12)=4213597Bell(12)=4213597，那么总操作次数大约是 4×106×12=5×1074\times10^6 ×12= 5\times10^7 次，这可能可以通过。例如，每个递归调用的处理时间非常短，没有复杂的运算，因此总的时间可能在 11 秒内。
因此，这个代码的思路是可行的，并且能够处理 n=12n=12 的情况，因为贝尔数的数量级是百万级别，而不是十亿级别。所以，这样的枚举方式在题目给出的约束下是可行的。
综上所述，该代码的正确性在于枚举所有可能的组分配方式，计算每个分组方式的异或和，并通过去重统计数目。虽然不同的组分配方式可能生成相同的异或和，但通过最后的排序和去重处理，得到正确的结果。该算法的时间复杂度在 n=12n=12 时是可行的，因为贝尔数的增长在可接受的范围内。
根据问题描述，我们需要确定在进行任意次数的石子转移操作后，所有可能的不同异或和的数量。每个操作允许我们将一个袋子的所有石子转移到另一个袋子。

方法思路

问题分析：

每次操作将两个袋子的石子合并，最终剩下的每个袋子中的石子数是若干原始袋子石子数的总和。
不同分组的石子总和异或后得到的可能值的数量即为所求。

关键观察：

不同的分组方式会产生不同的异或和。我们需要枚举所有可能的分组方式。
每个袋子可以被分配到任意一个组，组的顺序不影响异或结果，因此需要去重处理。

算法选择：

使用深度优先搜索（DFSDFS）枚举所有可能的分组方式。
对每个分组方式计算异或和，最后通过排序和去重统计不同结果的数量。
经过漫长思想斗争后，代码终于现身了，我也相信大部分人只会看这里

代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2.6e7;
int n,cnt,a[13],b[13],opt[13],ans[MAXN];
void dfs(int tmp,int maxn){
	if(tmp==n){
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++)b[opt[i]]+=a[i];
		int res=0;
		for(int i=1;i<=n;i++)res^=b[i];
		ans[++cnt]=res;
		return;
	}
	for(int i=1;i<=maxn+1;i++){
		opt[tmp+1]=i;
		dfs(tmp+1,max(i,maxn));
	}
}
signed main(){
	cin >> n;
	for(int i=1;i<=n;i++)cin >> a[i];
	opt[1]=1;
	dfs(1,1);
	sort(ans+1,ans+cnt+1);
	cnt=unique(ans+1,ans+cnt+1)-ans-1;
	cout << cnt;
	return 0;
}

补充解释

  1. 变量定义：
  • MAXNMAXN 设置为足够大的值以存储可能的异或结果。
  • aa 数组存储输入的每个袋子的石子数。
  • optopt 数组记录每个袋子被分配到的组号。
  • ansans 数组存储所有可能的异或结果。
  1. DFSDFS 函数：
  • tmptmp 表示当前处理的袋子索引，maxnmaxn 表示当前最大的组号。
  • 递归枚举每个袋子可能被分配到的组号（现有组或新组）。
  • 当处理完所有袋子后，计算当前分组的异或和并存入结果数组。
  1. 主函数：
  • 读取输入并初始化第一个袋子的组号。
  • 调用 DFSDFS 枚举所有分组方式。
  • 对结果数组排序并去重，最后输出不同结果的数量。
该方法通过 DFSDFS 枚举所有可能的分组方式，并利用异或的性质和去重操作高效地统计不同异或值的数量。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...