GP of Tokyo D. Xor Sum

问题需要求的是 “最大值最小”，可以想到二分答案 $V$，变成判定性问题。

XOR 运算的每一位是独立的，由此我们先独立地考虑每一位。假设第 $i$ 位有 $c_i \ (c_i\le n)$ 个数为 $1$，那么 $X$ 变成限制所有 $c_i$ 的奇偶性。

设 $b_i$ 为 $(S-X)/2$ 的第 $i$ 位（如果 $S<X$ 或 $S-X$ 是奇数先特判），可以发现 $c_i = 2 b_i + x_i$ 是一组合法的初始解。同时，所有的解可以通过不断操作 「$c_i$ 减二，$c_{i-1}$ 加四」来得到。

加下来的方向可能也只有按数位从高到低 DP 了。有了 $V$ 的限制之后，我们让状态的第二维为「当前有多少个 $a_i$ 未卡到 $V$ 的上界」，称其为 “自由位”。设 $f(i,j)$ 为：当前考虑第 $i$ 位，有 $j$ 个 $a_i$ 卡到上界，最少需要多少进位（也即当前位操作数量）。可以做到关于 $n$ 和 $\log V$ 的多项式复杂度。

考虑缩小 $j$ 的状态数量。一个重要的性质是，如果「当前 $V_i$ 是 $1$，自由位的数量至少为 $3$，同时不需要进位」，那么 $V$ 一定可行。这是因为 $c_i$ 的初始解 $\le 3$，一旦有 $3$ 个数成为自由位，可以令后面的其他位都是 $0$，由这 $3$ 个数字自由调整。

设之前退下来的位加上当前的初始解为 $w$，也即当前位需要的 $1$ 的个数（可以继续往后退）。如果当前 $V_i$ 为 $0$，那么只能继续往后退。接下来，如果 $w \le n$ 并且 $\min(n-w+j,n) \ge 3$，直接返回 true（由前一段所述）。否则继续枚举 $k$，表示新的自由位个数。继续观察可以发现一个更重要的性质：当 $k\ge 5$ 的时候，如果 $k-j \ge 2$ 显然是更不优的（由于奇偶性的限制，$2$ 到 $4$ 的转移是必要的），当 $j$ 足够大的时候，我们最优化的目标只有 需要的进位最少。

所以需要考虑的 $j$ 的上界只有 $5 + \log S$... 由此我们得到了一个 $O(\log^3S)$ 的做法。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lc (o<<1)
#define rc (o<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
template<class T> void read(T &x){
    int f=0; x=0; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
const ll inf=2e18;
const int N=70;
ll f[N],g[N];
//j>=3且没有进位时，直接返回1
//j较大时，显然最多j只会增加1
int chk(ll n,ll s,ll x,ll v){
    s-=x;
    if(s<0||s%2) return 0;
    s/=2;
    int m=min(3ll,n);
    REP(i,N) f[i]=inf;
    f[0]=0;
    per(i,60,0){
        REP(j,N) g[j]=inf;
        rep(j,0,m){
            ll now=f[j]*4+(x>>i&1)+(s>>i&1)*2;
            if(!(v>>i&1)){
                ll e=(max(now-j,0ll)+1)/2;
                if(e*2<=now) g[j]=min(g[j],e);
                continue;
            }
            if(now<=n&&min(n-now+j,n)>=3) return 1;
            for(int k=j;k<=n&&(k<5||k-j<=1);k++){
                ll u=n-k+j;
                if(u>=now%2){
                    ll e=now-min(now,(u-now%2)/2*2+now%2);
                    g[k]=min(g[k],e/2);
                }
            }
        }
        m=min(m+1ll,n);
        swap(f,g);
    }
    rep(i,0,m) if(!f[i]) return 1;
    return 0;
}
void rmain(){
    ll n,s,x;
    cin>>n>>s>>x;
    ll l=0,r=s+1;
    while(l<r){
        ll m=(l+r)>>1;
        if(chk(n,s,x,m)) r=m;
        else l=m+1;
    }
    cout<<(l==s+1?-1:l)<<endl;
}
int main(){
    int T; read(T);
    while(T--) rmain();
    return 0;
}