「题解」「CF1325D」Ehab the Xorcist

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

题目链接:Codeforces 1325D


系列题解:
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;
}