题解：AT_abc390_d [ABC390D] Stone XOR

xyx4042025-02-032025-02-19

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

题意：

给定 $N$ 个袋子，每个袋子里有若干石子。每次操作可以选择两个袋子，将其中一个的所有石子倒入另一个。求所有操作结束后，各袋子石子数的异或和有多少种不同的可能值。

思路：

观察发现最终异或和的值仅与分组方式有关。每次合并操作相当于将两个袋子的石子合并为一个新的袋子，最终的分组可以看作将初始的 $N$ 个袋子划分成若干非空子集，每个子集的石子总和构成最终的异或和。

可以通过动态规划逐步生成所有可能的分组方式。

处理每个石子堆时，对当前所有可能的状态进行扩展：

新增分组，将当前石子堆作为独立分组。
合并到已有分组，将当前石子堆合并到任意一个已有分组中。

最后进行去重统计。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n;
vector<LL>A(20);
vector<pair<vector<LL>,LL> >cur;
unordered_set<LL>ans;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>A[i];
	cur.emplace_back(vector<LL>{A[0]},A[0]);
	for(int i=1;i<n;i++){
		vector<pair<vector<LL>,LL> >tamp;
		for(auto g:cur){
			vector<LL>zhu=g.first;
			LL v=g.second;
			// 新增分组
			vector<LL>newg=zhu;
			newg.emplace_back(A[i]);
			LL nv=v^A[i];
			tamp.emplace_back(newg,nv);
			// 合并到已有分组
			for(int j=0;j<zhu.size();j++){
				vector<LL>temp(zhu);
				temp[j]+=A[i];
				LL val=v^zhu[j]^temp[j];
				tamp.emplace_back(temp,val);
			}
		}
		cur=tamp;
	} 
	for(auto g:cur){
		LL v=g.second;
		ans.insert(v);
	}
	cout<<ans.size();
	return 0;
}

AC 记录。