题解：AT_abc390_d [ABC390D] Stone XOR

yuzipeng · 2025-02-01 13:05:07 · 题解

题目传送门

atcoder

洛谷

拿到一道题，首先思考：

题目是说有 N 个袋子，每个袋子里有若干石头。我们可以进行任意次数的操作，每次选两个袋子 A 和 B，把 A 的所有石头移动到 B 里。最后，每个袋子的石头数 B_i 的异或和有多少种不同的可能值。输出这个数量。

首先，我得理解操作的结果。每次操作可以合并两个袋子，比如把 A 的石头全给 B。经过多次操作后，最终的袋子分布其实是把原来的袋子分成了若干个组，每个组的石头总和被分配到某个袋子中。比如，假设最后剩下 k 个袋子，那么每个袋子里的石头总和是原来某些袋子的总和。比如，最初的每个袋子 i 的石头总和会被合并到某个最终的袋子里。

那这个时候，问题可以转化为，如何将所有袋子分成若干个非空的不相交的组，每个组的和作为该组的贡献，然后将这些组的数值异或起来。不同的分组方式会得到不同的异或和。我们需要找出所有可能的分组方式对应的异或值的不同数量。

那问题就转化为，枚举所有可能的分组方式，计算它们的异或和，然后统计不同的值的数量。

但怎么枚举所有可能的分组呢？比如，当 N=3 的时候，分组可以是三个单独的，或者两个合并成一个，或者全部合并成一个。不同的分组方式对应不同的异或结果。

那这个时候，每个分组方式可以看作是将原数组 A 划分成一个集合的子集，每个子集至少有一个元素，且所有子集的并集是全集。每个子集的和作为异或的一个元素。然后，这些子集的和异或的结果就是最终的值。

但是，这样的划分方式可能有多种，比如不同的划分结构。比如，当 N=3 时，可能的划分结构包括：三个单独的分组，两个分组（比如袋子 1 和 2 合并，袋子 3 单独），或者一个分组。不同的结构对应不同的异或结果。

那这个时候，问题就转化为，如何枚举所有可能的子集划分，然后计算每个划分对应的异或总和，最后统计不同结果的数量。

但这样的枚举方式在 N=12 的时候会不会很困难呢？因为 N 是 12，可能的划分数是贝尔数，贝尔数的第十二项是 4213597，这在千万级别。那对于每个划分，我们需要计算异或总和，然后将这些总和存入集合中，最后统计数量。这似乎对于 N=12 来说，贝尔数可能超过 10^8 的话，可能会有问题，比如时间不够或者内存不足。但是看样例中的第三个测试样例输出是 84 ，可能实际可行的分组方式并没有那么多？

或者，可能题目中的某些性质可以减少计算量。比如，异或的性质可能允许某些不同的分组方式得到相同的异或结果，因此不需要枚举所有可能的划分，而是可以找到一种更高效的方式。

那回到代码（见下）。它用了深度优先搜索的方式，对于每个袋子，选择它属于哪个组。比如，opt 数组记录每个袋子被分配到哪个组。例如，opt[i] = k 表示第 i 个袋子被分配到第 k 个组。这里的组是按顺序编号的，比如第一个袋子必须分到组 1，第二个袋子可以分到组 1 或者组 2，第三个袋子可以分到已有的组或者新组，等等。这样，不同的 opt 数组的排列对应不同的分组方式，但可能会有重复的情况。比如，组编号的排列顺序不影响分组的实际结构，比如组 1 和组 2 的顺序调换，但分组方式相同的话，它们的异或结果是一样的。所以，这样的枚举方式可能会导致重复计算吗？

比如，假设两个分组方式的结构是相同的，只是组的编号不同，那么它们的异或结果可能相同。例如，假设袋子 1 和袋子 2 被分到组 1，袋子 3 被分到组 2，或者袋子 1 分到组 2，袋子 2 分到组 2，袋子 3 分到组 1。这种情况下，它们的异或和会是相同的，因为异或的顺序不影响结果。因此，这样的不同 opt 数组对应的分组方式会被视为不同的情况，但实际它们的异或结果相同。那么，在代码中，如何处理这种情况？

看代码中的 dfs 函数，opt 数组存储每个袋子被分配到的组号，比如，对于 n=3 的情况，可能的 opt 数组可能是 [1,1,2]，或者 [1,2,1]，这会被视为不同的分组方式吗？是的。但是，在计算异或的时候，组的顺序不影响异或的结果，因为异或是交换的。所以，这两种不同的 opt 数组对应的异或和是一样的。那么，这样就会导致在 ans 数组中存入重复的值，最终通过排序去重来得到正确的数量。

所以，这个算法的思路是枚举所有可能的组分配方式，不管组的顺序如何，然后将它们的异或和存入数组，最后去重统计数量。因为不同的组分配方式可能生成相同的异或结果，所以通过 unique 处理后的结果就是正确的答案数量。

那这个算法的时间复杂度如何？比如，对于每个袋子 i，选择它所在的组的编号。而组的编号不能超过当前的最大值加一。例如，第一个袋子必须分到组 1。第二个袋子可以分到组 1 或组 2。第三个袋子可以分到组 1、组 2 或组 3，或者如果前面的组的最大是 2，那么可以分到现有的或者新增的组 3。这样，这种枚举方式实际上生成了所有可能的非空划分，其中组的顺序被考虑，但异或的顺序不影响结果。

所以，这样的枚举方式会产生很多重复的分组结构，即不同组的顺序会被视为不同的情况，但它们的异或结果可能相同。所以，这样的枚举方式虽然会生成很多重复的异或结果，但最终通过 unique 去重，得到正确的答案。

例如，对于 n=3 的情况，不同的分组方式的数量等于贝尔数，也就是 5 种可能的分组方式。但通过这种枚举方式，可能生成的 opt 数组的数量比贝尔数大。例如，贝尔数是 5，而该算法枚举的可能更多？

比如，n=3 时，分组方式的数量是 5 种。但是根据这种枚举方式，每个分组方式对应的组编号可能不同。例如，对于分组方式 \left \{ \left \{ 1 \right \} ,\left \{ 2 \right \} ,\left \{ 3 \right \} \right \} ，对应的组编号可以是 1、2、3，或者其他排列吗？

比如，假设第一个袋子分配到组 1，第二个袋子可以选择组 1 或组 2。假设选择组 2，第三个袋子可以选择组 1、组 2 或组 3。如果选择组 3，那么分组是三个单独的。或者，对于第三个袋子，如果第二个袋子分配到组 2，第三个袋子可以选择组 2 的话，那么分组是 \left \{ 1\right \} ，\left \{ 2,3 \right \} 。或者，如果第三个袋子分配到组 1，那么分组是 \left \{ 1,3\right \} ，\left \{ 2\right \} 。所以，这种方式枚举的是所有可能的组分配，其中组的编号是按顺序分配的。因此，这种方式确实枚举了所有可能的分组结构，不管组的顺序如何。例如，对于分组结构是合并袋子 1 和袋子 2 的情况，对应的组编号可能是组 1、1、2（如果第三个袋子分配到组 2），或者组 1、1、3（如果第三个袋子分配到新的组 3），但异或的结果是相同的，因为组的顺序不影响异或的结果。因此，不同的 opt 数组可能生成相同的异或和，但通过最终的 unique 处理，得到正确的结果。

因此，这个算法的正确性基于：枚举所有可能的分组方式的异或和，然后去重得到不同的值。虽然枚举的方式可能产生不同的 opt 数组，但它们对应的异或和可能相同，但最终会被 unique 处理掉，所以结果正确。

那这个算法的时间复杂度如何？例如，当 n=12 时， opt 的可能情况有多少种？这应该等于递推的贝尔数吗？或者可能更高？

这里，每个袋子 i 的选择是：可以分配到前面的任何一个已经存在的组（组的编号不超过当前的最大值），或者创建一个新的组（当前最大值 +1）。例如，对于第 i 个袋子，它可选的组的数量等于当前的最大组数 +1。而每次选择的时候，maxn 是当前的最大组号。例如，当处理到第 i 个袋子时，假设前 i-1 个袋子的组分配的最大组号是 k，那么第 i 个袋子可以选择 1 到 k+1 中的任意一个。

这种递归的方式生成的 opt 数组的数量等于增长数（或者叫做 Fubini 数，或者排列的贝尔数）。例如，对于 n=3，这等于 13 种可能的分配方式。例如，这个数比贝尔数大，因为贝尔数是 5 种分组方式，而这里可能生成的分配方式数目更大，因为不同的组的顺序被视为不同的情况。例如，在分组结构相同的情况下，不同的组顺序会被视为不同的分配方式，从而导致不同的 opt 数组，但异或结果相同。

例如，n=3 时，该算法枚举的分组方式数目等于 13。而贝尔数是 5。这说明该算法生成的 opt 数组数目大于等于贝尔数，但每个分组结构对应多个 opt 数组，所以最终生成的异或结果数目可能等于正确的数目，因为不同的结构可能得到不同的结果，但同一结构的不同排列方式可能得到相同的结果，从而被去重处理。

所以，当 n=12 时，这个算法的复杂度可能很高。比如，Fubini 数是随着 n 的增大而指数级增长的。比如，当 n=12 时，Fubini 数是 4213597 × ...？或者可能更高？比如，根据维基百科，Fubini 数（有序贝尔数）的第 12 项是 4213597 × ...？或者可能更高？例如，已知 Fubini 数的前几项是 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ...。当 n=12 时，这个数可能非常大，比如超过 10^8？如果是这样的话，这样的算法在 n=12 的时候可能会超时或者超内存。

例如，样例输入 3 的输出是 84，这说明当 n=6 时，可能的异或结果数目是 84。这说明，虽然可能的分组方式数目很大，但不同的分组方式可能生成相同的异或结果，所以最终数目可能较低。

但是，根据代码中的 ans 数组的大小是 2.6\times10^7。而 cnt 变量在 n=12 的时候可能会超过这个值，导致数组越界或者错误？

比如，在代码中，MAXN 是 2.6\times10^7。如果当 n=12 时，Fubini 数是约 4\times10^8，显然这会超过 MAXN 的大小，导致数组溢出。这说明，这个代码可能在较大的测试用例中无法通过，比如 n=12 时会导致 ans 数组溢出，或者导致运行时间过长。

但是，观察样例输入 2 的输出是 2。这说明，当两个袋子的时候，可能的异或结果数目是 2。而根据分组方式，可能只有两种可能：两个袋子各自单独，异或和为 A_1 \oplus A_2；或者两个袋子合并，异或和为 A_1 + A_2。所以，当两个袋子时，可能的异或结果数目是 2。这说明，该代码在 n=2 时是正确的。

这说明，该代码可能在测试用例的约束下是正确的，但可能对于 n=12 的情况无法处理。然而，在题目给出的约束中，n≤12，且代码的 ans 数组的大小是 2.6\times10^7，那么这可能意味着在某些情况下，例如 n=12 时，代码无法处理，但可能实际运行通过了？或者可能存在其他优化？

或者，可能问题的实际可行解数目较小，所以虽然分组方式数目很大，但不同的方式可能生成相同的异或结果，导致 ans 数组中的实际数目不超过 MAXN 的限制。例如，当 n=12 时，可能不同的分组方式的异或结果数目在 2.6\times10^7 以内，所以不会溢出。

或者，可能该代码在 n=12 时，实际上生成的 ans 数组的大小不会超过 MAXN 的限制。比如，当 n=12 时，Fubini 数是 4213597，这大约是四百万，而每个分组方式的异或结果可能有很多重复，所以 ans 数组的数目可能远小于这个数值。例如，当每个分组方式的异或结果都是唯一的，那么当 n=12 时，ans 数组需要存储四百万个数，而 MAXN 是 2.6\times10^7，足够容纳。这样，代码是正确的。

那现在，我们需要理解这个代码的具体实现。代码中的 dfs 函数是递归的，每次处理一个袋子，选择其所属的组号。opt 数组保存每个袋子所属的组号。例如，opt[i] 的值是袋子 i 被分到的组的编号。当递归到第 tmp 个袋子时，maxn 是目前最大的组号。

例如，当处理到第 tmp+1 个袋子时，可以选择将其分配到现有的任何一个组（1 到 maxn），或者创建一个新的组（maxn+1）。然后递归下去。这样，所有可能的组分配方式都被枚举，其中组的顺序是无关的，但不同的分配方式可能生成相同的分组结构，只是组的顺序不同。

当处理到 n 个袋子后，opt 数组中的所有元素都被确定。此时，代码中的 b 数组保存每个组的石头总和。例如，b 数组的下标是组号，对应的值是所有分配到该组的袋子的石头总和。然后，将这些组的异或和计算出来，存入 ans 数组中。

例如，假设袋子 1 和袋子 2 被分配到组 1，袋子 3 被分配到组 2，那么 b[1] = a[1] + a[2] ，b[2] = a[3]。异或和是 b[1] ^ b[2]。而如果袋子 1 和袋子 2 被分配到组 2，袋子 3 被分配到组 1，那么 b[2] = a_1+a_2，b[1] = a_3，异或和还是相同的。所以，这样的不同分配方式会被视为不同的情况，但它们的异或和相同，因此在 ans 数组中会被存入相同的数值，最后通过 unique 处理得到正确的数目。

因此，这个算法的正确性是正确的，因为它枚举了所有可能的组分配方式，然后计算异或和，并通过去重得到数目。但问题是，当 n=12 时，这样的枚举是否可行？

比如，对于 n=12，每个袋子有多个选择，每个选择生成不同的路径。但这样的递归深度是 12 层，对于每个袋子来说，选择的组数目可能很大。例如，第一个袋子只能选组 1。第二个袋子可以选组 1 或组 2。第三个袋子可以选组 1、组 2 或组 3，依此类推。假设每个袋子最多有 k 组的选择，那么总的时间复杂度可能是 O(n!)，但实际上可能更高，比如 O(n^n)，这在 n=12 时是很大的数值。例如，n=12 时，这样的枚举次数可能高达 12!，或者更高。这显然会导致超时。

那为什么这个代码能通过呢？比如，可能题目中的测试用例没有 n=12 的情况，或者该算法的时间复杂度实际上在 n=12 时是可行的？

或者，可能这个问题的正确解法并不是通过枚举所有分组方式，而是利用了异或的某些性质，从而可以快速计算可能的结果数目。比如，将问题转化为线性基的问题，或者通过动态规划的方式。

但是，当前的代码显然是通过枚举所有分组方式，并统计异或结果的数目。这可能适用于 n 较小的场合，比如 n=12 时，可能实际的运行时间在可接受的范围内？

或者，可能该代码的时间复杂度在 n=12 时是可行的，因为每组选择的方式数可能被优化。例如，当 n=12 时，每个袋子 i 的选择可能最多有 i 种组的可能性，那么总的选择次数是 1×2×3×...×12= 12! = 479001600，这大约是 5\times10^8 次，显然超过时间限制。但代码中的 MAXN 是 2.6\times10^7，而 ans 数组的大小是 2.6\times10^7，可能无法存储这么大的数目。这显然存在矛盾。

那这代码是否真的能处理 n=12 的情况？

可能，这个问题的正确解法是基于分组方式的异或和的性质，允许通过某种数学方式快速计算可能的结果数目，而不是枚举所有可能的分组方式。例如，每个分组的异或和可以看作是某些线性基的组合，从而可以用动态规划来跟踪可能的异或结果。

但代码中的做法显然不是这样，而是直接枚举所有分组方式，这在 n=12 时可能不可行。所以，这说明该代码可能仅在 n 较小的情况下通过，而无法处理 n=12 的情况，但题目中的测试用例可能没有达到 n=12 的极限情况？

或者，可能这个问题的正确解法确实是枚举所有分组方式，但通过某种剪枝或优化，使得在 n=12 时也能快速处理？

例如，可能，虽然分组方式的数量是贝尔数的量级，但当 n=12 时，贝尔数大约是 4\times10^6，这可能在时间允许的范围内？比如，贝尔数 B(12) 是 4213597，所以当 n=12 时，代码中的 dfs 函数会被调用约 4\times10^6 次。每次调用会处理到 n 层，当 n=12 时，总的操作次数是大约 4e6 次，这可以处理的。例如，每个递归调用的操作是 O(n) 时间吗？比如，在递归到 tmp 层时，循环次数取决于 maxn 的当前值。例如，对于每个袋子 i，循环次数是 maxn+1，其中 maxn 是之前的组数。这可能平均下来每个递归调用的循环次数是较小的。例如，当 i=12 时，每个递归调用的循环次数可能平均为 log(n) 次。这样，总的操作次数可能在合理的时间范围内。

或者，可能这个代码的时间复杂度是 O(Bell(n) × n)，其中 Bell(n) 是贝尔数。当 n=12 时， Bell(12)=4213597，那么总操作次数大约是 4\times10^6 ×12= 5\times10^7 次，这可能可以通过。例如，每个递归调用的处理时间非常短，没有复杂的运算，因此总的时间可能在 1 秒内。

因此，这个代码的思路是可行的，并且能够处理 n=12 的情况，因为贝尔数的数量级是百万级别，而不是十亿级别。所以，这样的枚举方式在题目给出的约束下是可行的。

综上所述，该代码的正确性在于枚举所有可能的组分配方式，计算每个分组方式的异或和，并通过去重统计数目。虽然不同的组分配方式可能生成相同的异或和，但通过最后的排序和去重处理，得到正确的结果。该算法的时间复杂度在 n=12 时是可行的，因为贝尔数的增长在可接受的范围内。

根据问题描述，我们需要确定在进行任意次数的石子转移操作后，所有可能的不同异或和的数量。每个操作允许我们将一个袋子的所有石子转移到另一个袋子。

方法思路

问题分析：

每次操作将两个袋子的石子合并，最终剩下的每个袋子中的石子数是若干原始袋子石子数的总和。

不同分组的石子总和异或后得到的可能值的数量即为所求。

关键观察：

不同的分组方式会产生不同的异或和。我们需要枚举所有可能的分组方式。

每个袋子可以被分配到任意一个组，组的顺序不影响异或结果，因此需要去重处理。

算法选择：

使用深度优先搜索（DFS）枚举所有可能的分组方式。

对每个分组方式计算异或和，最后通过排序和去重统计不同结果的数量。

~~经过漫长思想斗争后，代码终于现身了，我也相信大部分人只会看这里~~

代码

#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;
}

补充解释

变量定义：

递归枚举每个袋子可能被分配到的组号（现有组或新组）。
当处理完所有袋子后，计算当前分组的异或和并存入结果数组。

主函数：

读取输入并初始化第一个袋子的组号。
调用 DFS 枚举所有分组方式。
对结果数组排序并去重，最后输出不同结果的数量。

该方法通过 DFS 枚举所有可能的分组方式，并利用异或的性质和去重操作高效地统计不同异或值的数量。