AT_abc347_d [ABC347D] Popcount and XOR

题目描述

给定非负整数 $a$、$b$、$C$。请判断是否存在满足以下 $5$ 个条件的非负整数对 $(X, Y)$，如果存在，请输出其中一组。

• $0 \leq X < 2^{60}$
• $0 \leq Y < 2^{60}$
• $\operatorname{popcount}(X) = a$
• $\operatorname{popcount}(Y) = b$
• $X \oplus Y = C$

其中，$\oplus$ 表示按位异或运算。

popcount 是什么？对于非负整数 $x$，$x$ 的 popcount 是指 $x$ 用二进制表示时 $1$ 的个数。更严格地说，对于非负整数 $x$，若 $x = \sum_{i=0}^{\infty} b_i 2^i \ (b_i \in \lbrace 0, 1 \rbrace)$，则 $\operatorname{popcount}(x) = \sum_{i=0}^{\infty} b_i$。

例如，$13$ 的二进制表示为 1101，所以 $\operatorname{popcount}(13) = 3$。

什么是按位异或？对于非负整数 $x, y$，$x, y$ 的按位异或 $x \oplus y$ 定义如下：

• $x \oplus y$ 的二进制表示中 $2^k\ (k \geq 0)$ 位，如果 $x, y$ 的二进制表示中 $2^k$ 位只有一方为 $1$，则该位为 $1$，否则为 $0$。

例如，$9, 3$ 的二进制分别为 1001, 0011，所以 $9 \oplus 3 = 10$（$10$ 的二进制为 1010）。

输入格式

输入为一行，包含三个整数：

$a$ $b$ $C$

输出格式

如果存在满足条件的非负整数对，则任选一组 $(X, Y)$，按顺序用空格分隔输出 $X$ 和 $Y$。如果不存在，输出 -1。

输入输出样例 #1

输入 #1

3 4 7

输出 #1

28 27

输入输出样例 #2

输入 #2

34 56 998244353

输出 #2

-1

输入输出样例 #3

输入 #3

39 47 530423800524412070

输出 #3

540431255696862041 10008854347644927

说明/提示

限制

• $0 \leq a \leq 60$
• $0 \leq b \leq 60$
• $0 \leq C < 2^{60}$
• 输入均为整数

样例解释 1

$(X, Y) = (28, 27)$ 满足条件。$X, Y$ 的二进制分别为 11100 和 11011。

• $X$ 的二进制为 11100，所以 $\operatorname{popcount}(X) = 3$。
• $Y$ 的二进制为 11011，所以 $\operatorname{popcount}(Y) = 4$。
• $X \oplus Y$ 的二进制为 00111，即 $X \oplus Y = 7$。

由于满足条件的整数对可能有多个，例如输出 42 45 也是正确答案。

样例解释 2

不存在满足条件的整数对。

样例解释 3

输出的值可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译