D. Ehab the Xorcist

Link: D. Ehab the Xorcist

Description

Given $2$ integers $u$ and $v$, find the shortest array such that bitwise-xor of its elements is $u$, and the sum of its elements is $v$.

Input
The only line contains $2$ integers $u$ and $v$ ($(0 \le u,v \le 10^{18})$).

Output
If there's no array that satisfies the condition, print "$-1$". Otherwise:

The first line should contain one integer, $n$, representing the length of the desired array. The next line should contain n positive integers, the array itself. If there are multiple possible answers, print any.

Examples
input
2 4
output
2
3 1
input
1 3
output
3
1 1 1
input
8 5
output
-1
input
0 0
output
0
Note
In the first sample, $3\oplus 1 = 2$ and $3+1=4$. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

Problem solving

这道题的意思就是给你两个数$u$,$v$,让你求一个最短的序列，满足序列中所有元素的异或和为$u$,所有的元素和为$v$,如果系列不存在就输出$-1$
分情况讨论

• 首先我们可以发现，如果$v < u$,答案不存在。我们按照二进制位来看，如果异或和中的某高位为$1$但是数值和小于$u$，也就是说肯定没有一个属可以让异或和的那个高位上为$1$，所以此时答案不存在
• 然后我们知道，如果$uv$的奇偶性各不相同，答案不存在。因为奇偶性只看最后一位，这时和异或正好是同步的。
• 然后我们考虑$u = v$的情况，如果此时$u=0$，那么输出$0$，否则，答案就是$[u]$。因为$uv$相等，序列中只有一个数，数值和与异或和均为它本身。所以与v也相等。
• 如果$u\neq v$,我们让$x=\frac{v-u}{2}$,那么此时的答案序列就是$[u,x,x]$,因为相等的数异或为$0$，$0$根任何数异或都为$0$，所以异或和为u，数值和为$u+2*x=u+2*\frac{v-u}{2}=v$。所以答案序列的长度最长为$3$。
• 我们考虑序列长度为2的时候，设序列为$[a,b]$,则$a \oplus b=u$且$a+b=v$，此时$a+b=a \oplus b+2*(a$&$b)$。所以我们发现上面我们定义的$x$正好等于$a$&$b$。如果$x$的某一位为$1$，那么$ab$的这一位一定也是$1$，那此时$u$的这一位为0，所以如果$u$这一位为$1$得时候，序列长度为2得时候显然不可以。（判断的话直接判断$x$&$u$是否为$1$即可）。如果$x$&$u=0$,那么我们可以得到$x \oplus u=x+u$，所以答案序列可以写成长度为2的$[u+x,x]$。

看了题解勉强可以看懂，但是自己想真的是想不起来2333。菜是原罪。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    ll u,v;
    cin>>u>>v;
    if(u>v||(u&1)!=(v&1)){
        puts("-1");
        return 0;
    }
    if(u==v){
        if(u==0){
            cout<<"0\n";
        }else{
            cout<<"1\n"<<u<<endl;
        }
        return 0;
    }
    ll x=(v-u)/2;
    if(x&u){
        cout<<"3\n"<<u<<" "<<x<<" "<<x;
    }else{
        cout<<"2\n"<<(u^x)<<" "<<x;
    }
    return 0;
}