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

· · 题解

link

Solution

注意到一个 ? 等价于这一位取 0 和 1 的广义子集和之和，注意到：

1 \le n \le 16

这个数据范围 2^n 甚至 3^n 都能过，考虑分治，把它按下标奇偶（也就是数字奇偶）分治，每次合并起来，复杂度就是传上来的数组大小，也就是 3^n。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18;
const i128 Inf=1e35;
vector<ll> solve(vector<ll> a,ll n)
{
    if(n==0)
    {
        vector<ll> ans;
        ans.push_back(a[0]);
        return ans;
    }
    ll hf=a.size()/2;
    vector<ll> odd,even;
    for(int i=0;i<hf;i++) odd.push_back(a[2*i+1]),even.push_back(a[2*i]);
    vector<ll> ansodd=solve(odd,n-1),anseven=solve(even,n-1);
    ll cnt=ansodd.size();
    vector<ll> ans(cnt*3);
    for(int i=0;i<cnt;i++) ans[3*i]=ansodd[i],ans[3*i+1]=anseven[i],ans[3*i+2]=ansodd[i]+anseven[i];
    return ans;
}
ll n,a,sum;
vector<ll> vec,ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=(1<<n);i++) cin>>a,vec.push_back(a);
    ans=solve(vec,n);
    for(auto v:ans) sum^=v;
    cout<<sum;
}

:::