Codeforces Round #628 (Div. 2) 一道比较中等的 二进制构造 题。

题目链接：Codeforces 1325D。

[toc]

系列题解：
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd；
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy；
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs；
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist；
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem；
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。

题目

原题

题意简述

给出 $u,v$ 要求构造一个正整数数列 $a_i$，满足：

• $\sum_\oplus a_i=u$
• $\sum a_i=v$

即数列的异或和为 $u$，和为 $v$。

同时，数列的长度要尽量小，无解输出 $-1$。

数据范围

$$0\leq u,v\leq 10^{18}$$

时空限制

见原题 pdf 文件。

题解

思路

首先可以发现，如果数列的异或和为 $u$，那么数列的和将 $\geq u$。

所以如果 $u>v$，则无解。

另外，如果 $u=v$，那么有两种情况：

1. $u=0$，直接输出 $0$；
2. $u\ne 0$，那么输出 $1$ 和 $u$。

下面着重考虑 $u$ 小于 $v$ 的情况。

首先发现，如果 $u$ 是奇数，那么对数列和的贡献中必然存在奇数个 $1$，所以 $v$ 也得是奇数。

进一步推导，可以得出 $u,v$ 的奇偶性相同是有解的充分必要条件。

下面构造解法。

构造

思考得到了一种巧妙的方法。

设 $c=\frac{v-u}{2}$，那么数列 $a$ 可以为 $c,c,u$，满足题意。

但我们考虑有没有 $n=2$ 的构造方法，答案当然是有的。

如果 $c\operatorname{and}u=0$，即 $c,u$ 在二进制意义下没有重叠，那么将它们相加，并不会进位，也不会干扰异或和的结果，而和不变。

所以当 $c\operatorname{and}u=0$ 时有更优的解法为 $c,c+u$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg ll res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

ll u,v;

int main(void){
    u=read(),v=read();
    if(u>v)
        puts("-1");
    else if(u==v){
        if(v==0)
            puts("0");
        else
            printf("1\n%lld\n",v);
    }
    else
        if((u&1)!=(v&1))
            puts("-1");
        else{
            reg ll x=(v-u)>>1;
            if((x&u)==0)
                printf("2\n%lld %lld\n",x,x+u);
            else
                printf("3\n%lld %lld %lld\n",x,x,u);
        }
    return 0;
}