题解：P12402 [COI 2025] 贪腐 / Korupcija

· · 题解

神秘构造题。

观察样例思考容易得到当 a_i 中有奇数时无解，当然特判一下 n=1。其它题解都没有说是为什么，其实原因很简单。考虑对于某一位，这一位数字为 1 的个数和 0 的个数都是总数的一半。那么每一次用掉一对数字，要么 0 的个数减 2，要么 1 的个数减 2，或者两个都减去 1。那么由于总数是偶数，第三种情况必须出现偶数次，贡献也就是偶数次了。

考虑如何构造方案。

我们尝试将大小为 n 的问题变为大小为 n-1 的子问题这样递归求解。求出大小为 n-1 的某个解后，在回溯的时候通过一些改变变为大小为 n 的解。

显然将 n 减 1 后，a_i 的总和减小一半，并且构造的数的范围也变为 0\sim 2^{n-1}-1。假设我们已经求出了某个 n-1 的解，要将其变换到 n 的解。我们显然要构造一种方法，使得可以生成第 n-1 位为 1 的数字对。

注意，我们在做大小为 n-1 的子问题时，只用了 0\sim 2^{n-1}-1 的数，还有一半的数没有用。思考一下，我们得到一种构造方案：

假设 n-1 的子问题中有一对数为 (x,y)，并且 x\oplus y=2^k，那么原本我们还可以构造 (x+2^{n-1},y+2^{n-1})，使其异或结果也为 2^k，这样就给 a_k 贡献了 2，我们试图将这 2 个贡献转移给 a_{n-1}。将两对数重新组合一下得到 (x,x+2^{n-1}) 和 (y,y+2^{n-1})。这样两对数异或结果都是 2^{n-1} 了。

现在我们完成了回溯要做的事，那么还剩下递归的时候如何把 a_{n-1} 的贡献分给其他位置。我们知道，分完后 a_0\sim a_{n-2} 均要减少一半，而减完一半后显然还需要满足这些都是偶数，即用 a_{n-1} 分完后，a_0\sim a_{n-2} 均为 4 的倍数。也就是说，如果分之前，存在 a_i 对 4 取余为 2，那么必须要由 a_{n-1} 分两个给 a_i。

显然，如果不够分就完蛋了。但由于位运算，每一位其实是独立的，所以我们可以找一个最大的 a_i 与 a_{n-1} 换一下，并记录下来，回溯的时候把每个数的这两个位置换回来就好了。

这个时候，a_{n-1} 的下界就是 \frac{2^{n-1}}{n}，而最差其他 n-1 个数都要分两个走，也就是要分 2(n-1) 个。注意到 a_{n-1} 是指数级别的，增长很快，所以不满足要求的 n 不会太大，n 最大是为 6，可以构造出一组不合法的数据：\{2,6,6,6,6,6\}。

所以很简单，在 n\le 6 的时候直接暴力搜索构造方案即可。

code：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
int id[25];
bool flag[70],ok;
set<p> s,tmps;
void dfs(int n,int k,vector<int> a){
    if(k==(1<<n)){
        ok=1;
        return;
    }
    if(flag[k]){
        dfs(n,k+1,a);
        return;
    }
    for(int j=0;j<n;j++){
        if(a[j]&&!flag[k^(1<<j)]){
            a[j]--;
            flag[k]=flag[k^(1<<j)]=1;
            s.insert({k,k^(1<<j)});
            dfs(n,k+1,a);
            if(ok) return;
            a[j]++;
            flag[k]=flag[k^(1<<j)]=0;
            s.erase({k,k^(1<<j)});
        }
    }
}
void work(int n,vector<int> a){
    if(n<=6){
        dfs(n,0,a);
        return;
    }
    int mx=0,mxid;
    for(int i=0;i<n;i++){
        if(a[i]>=mx){
            mx=a[i];
            mxid=i;
        }
    }
    swap(a[mxid],a[n-1]);
    int tmpf[25]={0};
    for(int i=0;i<n-1;i++){
        if((a[i]>>1)&1){
            tmpf[i]=1;
            a[i]+=2;
            a[n-1]-=2;
        }
    }
    a[n-2]+=a[n-1];
    tmpf[n-2]+=a[n-1]>>1;
    for(int i=0;i<n-1;i++){
        a[i]>>=1;
    }
    work(n-1,a);
    for(auto it=s.begin();it!=s.end();){
        int x=it->first,y=it->second;
        int w=__lg(x^y);
        if(tmpf[w]){
            tmpf[w]--;
            it=s.erase(it);
            s.insert({x,x^(1<<n-1)});
            s.insert({y,y^(1<<n-1)});
        }
        else{
            if(x<(1<<n-1)&&(y<(1<<n-1))){
                s.insert({x^(1<<n-1),y^(1<<n-1)});
            }
            it++;
        }
    }
    tmps.clear();
    for(auto it=s.begin();it!=s.end();it++){
        int x=it->first,y=it->second;
        x=x^(x&(1<<n-1))^(x&(1<<mxid))^((x>>n-1&1)<<mxid)^((x>>mxid&1)<<n-1);
        y=y^(y&(1<<n-1))^(y&(1<<mxid))^((y>>n-1&1)<<mxid)^((y>>mxid&1)<<n-1);
        tmps.insert({x,y});
    }
    s=tmps;
}
int main(){
    int n;
    vector<int> a;
    cin>>n;
    if(n==1){
        puts("0 1");
        return 0;
    }
    a.resize(n+1);
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]&1){
            cout<<-1;
            return 0;
        }
    }
    work(n,a);
    for(auto x:s){
        printf("%d %d\n",x.first,x.second);
    }
    return 0;
}