题解：AT_abc390_d [ABC390D] Stone XOR

· · 题解

题意：

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

思路：

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

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

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

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

最后进行去重统计。

代码：

#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 记录。