题目描述

难度分:$1041$

输入$a(0 \leq a \leq 60),b(0 \leq b \leq 60)$和$xor(0 \leq xor \lt 2^{60})$。

构造两个在$[0,2^{60})$中的整数$x$和$y$，满足$x$的二进制中有$a$个$1$，$y$的二进制中有$b$个$1$，且$x$异或$y$等于$xor$。

输出$x$和$y$。多解输出任意解。如果无法构造，输出$-1$。

输入样例$1$

3 4 7

输出样例$1$

28 27

输入样例$2$

34 56 998244353

输出样例$2$

-1

输入样例$3$

39 47 530423800524412070

输出样例$3$

540431255696862041 10008854347644927

算法

记忆化搜索

状态定义

$dp[i][a][b]$表示$[0,i-1]$位全部构造完，从第$i$位开始构造，$x$和$y$的二进制中分别有$a$个$1$和$b$个$1$的情况下，后面能否构造出符合$xor$从第$i$位到第$59$位的$x$和$y$，满足$x \oplus y=xor$。

状态转移

$base$ $case$分为以下两种：

1. 如果$i=60$时满足$a=b=0$，则$dp[i][a][b]=$true。
2. 如果$a \lt 0$或$b \lt 0$，则$dp[i][a][b]=$false。

一般情况分为以下两种：

1. 如果$xor$在第$i$位是$1$，那么$x$和$y$在这一位就不同，尝试让$x$在这一位为$1$，以及$y$在这一位为$1$，状态转移方程为$dp[i][a][b]=dp[i+1][a-1][b] \lor dp[i+1][a][b-1]$。
2. 如果$xor$在第$i$位是$0$，那么$x$和$y$在这一位就相同，尝试让$x$和$y$在这一位为$1$，以及$x$和$y$在这一位为$0$，状态转移方程为$dp[i][a][b]=dp[i+1][a-1][b-1] \lor dp[i+1][a][b]$。

记忆化搜索完成之后，只要$dp[0][a][b]=$true就有解，再从低位到高位进行一次$dfs$，根据$dp$状态构造出$x$和$y$。否则无解，直接输出$-1$。

复杂度分析

时间复杂度

状态数量为$O((log_2U)^3)$，$U$为$xor$的值域，单次转移的时间复杂度为$O(1)$。因此，整个算法的时间复杂度为$O((log_2U)^3)$。

空间复杂度

空间消耗的瓶颈就在于记忆化搜索时对DP状态的缓存，即为状态数量$O((log_2U)^3)$，这也是整个算法的额外空间复杂度。

python 代码

from functools import lru_cache

a, b, xor = map(int, input().split())
x, y = 0, 0

@lru_cache(None)
def dfs1(i: int, a: int, b: int) -> bool:
    if a < 0 or b < 0:
        return False
    if i == 60:
        return a == 0 and b == 0
    if xor>>i&1:
        # x和y在此位必须不同
        return dfs1(i + 1, a - 1, b) or dfs1(i + 1, a, b - 1)
    else:
        return dfs1(i + 1, a - 1, b - 1) or dfs1(i + 1, a, b)

def dfs2(i: int, a: int, b: int) -> None:
    if i == 60:
        return
    global x, y
    if xor>>i&1:
        if dfs1(i + 1, a - 1, b):
            x |= 1<<i
            dfs2(i + 1, a - 1, b)
        elif dfs1(i + 1, a, b - 1):
            y |= 1<<i
            dfs2(i + 1, a, b - 1)
    else:
        if dfs1(i + 1, a - 1, b - 1):
            x |= 1<<i
            y |= 1<<i
            dfs2(i + 1, a - 1, b - 1)
        elif dfs1(i + 1, a, b):
            dfs2(i + 1, a, b)

if dfs1(0, a, b):
    dfs2(0, a, b)
    print(x, y)
else:
    print(-1)