题解：P17124 [ICPC 2025 Shanghai R] Not a subset sum

Jin_2014 · 2026-07-19 21:27:00 · 题解

题意

给定长度为 2\times n 的数组 a。对于长度为 n、仅由字符 0、1、? 组成的查询字符串 q：

• 若 q_i=0：要求选中的下标 j 的第 i 位二进制必须是 0。
• 若 q_i=1：要求选中的下标 j 的第 i 位二进制必须是 1。
• 若 q_i=?：要求选中的下标 j 的第 i 位二进制没有限制。

设所有符合约束的下标的对应数组元素之和为该查询的广义子集和 S(q)，要求输出所有合法查询对应的所有 S(q) 的异或结果。

思路

可以逐层分治生成所有合法广义子集和‌：

1. ‌分解：
   将当前长度为 2^k 的数组平分为大小相等的两半，偶数下标组成左半数组、奇数下标组成右半数组，递归计算两半各自的所有合法广义子集和集合。
2. 合并：
   对于左右两半返回的子集和集合的同位置元素 - 左半独立生成的和 $x$，对应新增位被指定为某固定值的情况。 - 右半独立生成的和 $y$，对应新增位被指定为另一固定值的情况。 - 左右组合和 $x+y$，对应新增位为 `?`、无取值限制的情况。

3. 答案：
   由于递归每一层都会让生成的子集和集合长度扩大为原来的 3 倍，最终我们可以得到所有 3^n 个合法广义子集和，最后直接对所有和进行异或运算就能得到最终答案。

   时间复杂度：

   O(3^N)

   代码：

   #include<bits/stdc++.h>
   using namespace std;
   vector<int>s(const vector<int>&a,int n) 
   {
   // 当 n=0 时，数组长度为 1，直接返回该元素
   if(n==0)return a;
   // 将当前数组长度减半
   int m=a.size()>>1;
   
   // 分解数组：
   // a0 存储原数组 a 中偶数下标的元素
   // a1 存储原数组 a 中奇数下标的元素
   vector<int>a0(m),a1(m);
   for(int i=0;i<m;i++) 
   {
       a0[i]=a[i<<1];
       a1[i]=a[i<<1|1];
   }
   // 递归处理两半部分，分别得到它们的子集和集合
   vector<int>s0=s(a0,n-1),s1=s(a1,n-1);
   int len=s0.size();
   vector<int>ans;
   for(int i=0;i<len;i++) 
   {
       ans.push_back(s0[i]);          // 情况1：仅包含来自 a0 部分的贡献
       ans.push_back(s1[i]);          // 情况2：仅包含来自 a1 部分的贡献
       ans.push_back(s0[i]+s1[i]);    // 情况3：同时包含 a0 和 a1 部分的贡献
   }
   return ans;
   }
   int main() 
   {
   int n;
   cin>>n;
   int m=1<<n;
   vector<int>a(m);
   for(int i=0;i<m;i++)cin>>a[i];
   // 所有广义子集的和
   vector<int>ans=s(a,n);
   int sum=0;
   // 计算所有子集和的异或值
   for(int i:ans)sum^=i;
   cout<<sum;
   return 0;
   }