← 返回题目列表

Codeforces · 1770/F

F. Koxia 和序列

中文机器翻译题面 查看原题

Mari 有三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$。

如果满足以下条件,则称 $$$a$$$ 为 $$$n$$$ 非负整数的数组为好:

- $$$a_1+a_2+\ldots+a_n=x$$$,并且
- $$$a_1 \, | \, a_2 \, | \、\点\、| \, a_n=y$$$,其中$$$|$$$表示按位或运算。

一个好的数组的分数是 $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$ 的值,其中 $$$\oplus$$$ 表示按位异或运算。

Koxia 希望您找到所有好的数组的分数的总按位异或。如果没有好的数组,则输出$$$0$$$。

输入

输入的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n < 2^{40}$$$、$$$0 \leq x < 2^{60}$$$、$$$0 \leq y < 2^{20}$$$)。

输出

输出一个整数——所有好数组的分数的总按位异或。

示例

输入 #1

3 5 3

输出 #1

2

输入 #2

100 0 100

输出 #2

0

输入 #3

79877974817 749875791743978 982783

输出 #3

64

注意

在第一个测试用例中,总共有 $$$12$$$ 好的数组,如下所示。

- $$$[0,2,3]$$$、$$$[0,3,2]$$$、$$$[2,0,3]$$$、$$$[2,3,0]$$$、$$$[3,0,2]$$$ 和 $$$[3,2,0]$$$ — 得分为 $$$0 \oplus 2 \oplus 3 = 1$$$;
- $$$[1, 2, 2]$$$、$$$[2, 1, 2]$$$ 和 $$$[2, 2, 1]$$$ — 分数为 $$$1 \oplus 2 \oplus 2 = 1$$$;
- $$$[1, 1, 3]$$$、$$$[1, 3, 1]$$$ 和 $$$[3, 1, 1]$$$ — 分数为 $$$1 \oplus 1 \oplus 3 = 3$$$。

因此,分数的总按位异或为 $$$\underbrace{1 \oplus \ldots \oplus 1}_{9\text{ times}} \oplus 3 \oplus 3 \oplus 3 = 2$$$。

在第二个测试用例中,没有好的序列。输出应该是$$$0$$$。