310003: CF1770F. Koxia and Sequence
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Koxia and Sequence
题意翻译
给定非负整数 $n,x,y$，对于所有满足 $\sum_{i=1}^n a_i=x,\text{OR}_{i=1}^n a_i=y$，的序列 $\{a_n\}$。求 $\bigoplus_{i=1}^n a_i$ 的异或和。题目描述
Mari has three integers $ n $ , $ x $ , and $ y $ . Call an array $ a $ of $ n $ non-negative integers good if it satisfies the following conditions: - $ a_1+a_2+\ldots+a_n=x $ , and - $ a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n=y $ , where $ | $ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). The score of a good array is the value of $ a_1 \oplus a_2 \oplus \ldots \oplus a_n $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Koxia wants you to find the total bitwise XOR of the scores of all good arrays. If there are no good arrays, output $ 0 $ instead.输入输出格式
输入格式
The first line of input contains three integers $ n $ , $ x $ and $ y $ ( $ 1 \leq n < 2^{40} $ , $ 0 \leq x < 2^{60} $ , $ 0 \leq y < 2^{20} $ ).
输出格式
Output a single integer — the total bitwise XOR of the scores of all good arrays.
输入输出样例
输入样例 #1
3 5 3输出样例 #1
2输入样例 #2
100 0 100输出样例 #2
0输入样例 #3
79877974817 749875791743978 982783输出样例 #3
64说明
In the first test case, there are $ 12 $ good arrays totally as follows. - $ [0,2,3] $ , $ [0,3,2] $ , $ [2,0,3] $ , $ [2,3,0] $ , $ [3,0,2] $ and $ [3,2,0] $ — the score is $ 0 \oplus 2 \oplus 3 = 1 $ ; - $ [1, 2, 2] $ , $ [2, 1, 2] $ and $ [2, 2, 1] $ — the score is $ 1 \oplus 2 \oplus 2 = 1 $ ; - $ [1, 1, 3] $ , $ [1, 3, 1] $ and $ [3, 1, 1] $ — the score is $ 1 \oplus 1 \oplus 3 = 3 $ . Therefore, the total bitwise xor of the scores is $ \underbrace{1 \oplus \ldots \oplus 1}_{9\text{ times}} \oplus 3 \oplus 3 \oplus 3 = 2 $ . In the second test case, there are no good sequences. The output should be $ 0 $ .Input
题意翻译
给定非负整数 $n,x,y$，对于所有满足 $\sum_{i=1}^n a_i=x,\text{OR}_{i=1}^n a_i=y$，的序列 $\{a_n\}$。求 $\bigoplus_{i=1}^n a_i$ 的异或和。Output
**小岛和序列**
**题目大意：**
给定非负整数 $ n, x, y $，对于所有满足 $ \sum_{i=1}^n a_i = x $ 且 $ \bigvee_{i=1}^n a_i = y $ 的序列 $ \{a_n\} $。求 $ \bigoplus_{i=1}^n a_i $ 的异或和。
**题目描述：**
Mari有三个整数 $ n $, $ x $, 和 $ y $。
称一个包含 $ n $ 个非负整数的数组 $ a $ 是好的，如果它满足以下条件：
- $ a_1 + a_2 + \ldots + a_n = x $，且
- $ a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n = y $，其中 $ | $ 表示按位或操作。
一个好的数组的分数是 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n $ 的值，其中 $ \oplus $ 表示按位异或操作。
小岛想要你找出所有好的数组的分数的按位异或总和。如果没有好的数组，则输出 $ 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 $。**小岛和序列** **题目大意：** 给定非负整数 $ n, x, y $，对于所有满足 $ \sum_{i=1}^n a_i = x $ 且 $ \bigvee_{i=1}^n a_i = y $ 的序列 $ \{a_n\} $。求 $ \bigoplus_{i=1}^n a_i $ 的异或和。 **题目描述：** Mari有三个整数 $ n $, $ x $, 和 $ y $。 称一个包含 $ n $ 个非负整数的数组 $ a $ 是好的，如果它满足以下条件： - $ a_1 + a_2 + \ldots + a_n = x $，且 - $ a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n = y $，其中 $ | $ 表示按位或操作。 一个好的数组的分数是 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n $ 的值，其中 $ \oplus $ 表示按位异或操作。 小岛想要你找出所有好的数组的分数的按位异或总和。如果没有好的数组，则输出 $ 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 $。
**题目大意：**
给定非负整数 $ n, x, y $，对于所有满足 $ \sum_{i=1}^n a_i = x $ 且 $ \bigvee_{i=1}^n a_i = y $ 的序列 $ \{a_n\} $。求 $ \bigoplus_{i=1}^n a_i $ 的异或和。
**题目描述：**
Mari有三个整数 $ n $, $ x $, 和 $ y $。
称一个包含 $ n $ 个非负整数的数组 $ a $ 是好的，如果它满足以下条件：
- $ a_1 + a_2 + \ldots + a_n = x $，且
- $ a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n = y $，其中 $ | $ 表示按位或操作。
一个好的数组的分数是 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n $ 的值，其中 $ \oplus $ 表示按位异或操作。
小岛想要你找出所有好的数组的分数的按位异或总和。如果没有好的数组，则输出 $ 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 $。**小岛和序列** **题目大意：** 给定非负整数 $ n, x, y $，对于所有满足 $ \sum_{i=1}^n a_i = x $ 且 $ \bigvee_{i=1}^n a_i = y $ 的序列 $ \{a_n\} $。求 $ \bigoplus_{i=1}^n a_i $ 的异或和。 **题目描述：** Mari有三个整数 $ n $, $ x $, 和 $ y $。 称一个包含 $ n $ 个非负整数的数组 $ a $ 是好的，如果它满足以下条件： - $ a_1 + a_2 + \ldots + a_n = x $，且 - $ a_1 \, | \, a_2 \, | \, \ldots \, | \, a_n = y $，其中 $ | $ 表示按位或操作。 一个好的数组的分数是 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n $ 的值，其中 $ \oplus $ 表示按位异或操作。 小岛想要你找出所有好的数组的分数的按位异或总和。如果没有好的数组，则输出 $ 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 $。