309870: CF1748F. Circular Xor Reversal
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Circular Xor Reversal
题意翻译
### 题目描述 给定整数 $n$。 初始，有一个编号从 $0$ 开始的长度为 $n$ 的环形序列 $a$，满足 $a_i=2^i$ 对任意整数 $i(0\leq i<n)$ 成立。 你的任务是将 $a$ 翻转，即使序列 $a$ 满足 $a_i=2^{n-i-1}$ 对任意整数 $i(0\leq i<n)$ 成立。 为此，你可以进行下列操作至多 $2.5\times10^5$ 次： - 选定整数 $i$，将 $a_i$ 的值改为 $a_i\text{ xor }a_{(i+1)\bmod n}$。 其中 $\text{xor}$ 表示按位异或运算。 可以证明在题目限制下，本题一定有解。你需要找出任意一组满足要求的解。 ### 输入格式 输入一行一个整数 $n(2\leq n\leq 400)$。 ### 输出格式 首先输出一行一个整数 $k(0\leq k\leq2.5\times10^5)$ 表示你所构造的操作方案的操作次数。 接下来输出一行 $k$ 个整数表示你每次操作所选择的 $i(1\leq i\leq n)$。 你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。 ### 样例解释 - 对于样例一： - 初始 $a$ 为 $[1,2]$。 - 第一次操作选择 $i=1$，操作后 $a$ 为 $[1,3]$。 - 第二次操作选择 $i=0$，操作后 $a$ 为 $[2,3]$。 - 第三次操作选择 $i=1$，操作后 $a$ 为 $[2,1]$，此时目标达成。 - 对于样例二： - 下面展示了样例输出对应的流程： $[1,2,4]\rightarrow[1,6,4]\rightarrow[7,6,4]\rightarrow[7,2,4]\rightarrow[5,2,4]\rightarrow[5,2,1]\rightarrow[5,3,1]\rightarrow[6,3,1]\rightarrow[6,2,1]\rightarrow[4,2,1]$。题目描述
You have an array $ a_0, a_1, \ldots, a_{n-1} $ of length $ n $ . Initially, $ a_i = 2^i $ for all $ 0 \le i \lt n $ . Note that array $ a $ is zero-indexed. You want to reverse this array (that is, make $ a_i $ equal to $ 2^{n-1-i} $ for all $ 0 \le i \lt n $ ). To do this, you can perform the following operation no more than $ 250\,000 $ times: - Select an integer $ i $ ( $ 0 \le i \lt n $ ) and replace $ a_i $ by $ a_i \oplus a_{(i+1)\bmod n} $ . Here, $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Your task is to find any sequence of operations that will result in the array $ a $ being reversed. It can be shown that under the given constraints, a solution always exists.输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 2 \le n \le 400 $ ) — the length of the array $ a $ .
输出格式
On the first line print one integer $ k $ ( $ 0 \le k \le 250\,000 $ ) — the number of operations performed. On the second line print $ k $ integers $ i_1,i_2,\ldots,i_k $ ( $ 0 \le i_j \lt n $ ). Here, $ i_j $ should be the integer selected on the $ j $ -th operation. Note that you don't need to minimize the number of operations.
输入输出样例
输入样例 #1
2输出样例 #1
3
1 0 1输入样例 #2
3输出样例 #2
9
1 0 1 0 2 1 0 1 0说明
In the notes, the elements on which the operations are performed are colored red. In the first test case, array $ a $ will change in the following way: $ [1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1] $ . In the second test case, array $ a $ will change in the following way: $ [1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,2,1] $ .Input
题意翻译
### 题目描述 给定整数 $n$。 初始，有一个编号从 $0$ 开始的长度为 $n$ 的环形序列 $a$，满足 $a_i=2^i$ 对任意整数 $i(0\leq i<n)$ 成立。 你的任务是将 $a$ 翻转，即使序列 $a$ 满足 $a_i=2^{n-i-1}$ 对任意整数 $i(0\leq i<n)$ 成立。 为此，你可以进行下列操作至多 $2.5\times10^5$ 次： - 选定整数 $i$，将 $a_i$ 的值改为 $a_i\text{ xor }a_{(i+1)\bmod n}$。 其中 $\text{xor}$ 表示按位异或运算。 可以证明在题目限制下，本题一定有解。你需要找出任意一组满足要求的解。 ### 输入格式 输入一行一个整数 $n(2\leq n\leq 400)$。 ### 输出格式 首先输出一行一个整数 $k(0\leq k\leq2.5\times10^5)$ 表示你所构造的操作方案的操作次数。 接下来输出一行 $k$ 个整数表示你每次操作所选择的 $i(1\leq i\leq n)$。 你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。 ### 样例解释 - 对于样例一： - 初始 $a$ 为 $[1,2]$。 - 第一次操作选择 $i=1$，操作后 $a$ 为 $[1,3]$。 - 第二次操作选择 $i=0$，操作后 $a$ 为 $[2,3]$。 - 第三次操作选择 $i=1$，操作后 $a$ 为 $[2,1]$，此时目标达成。 - 对于样例二： - 下面展示了样例输出对应的流程： $[1,2,4]\rightarrow[1,6,4]\rightarrow[7,6,4]\rightarrow[7,2,4]\rightarrow[5,2,4]\rightarrow[5,2,1]\rightarrow[5,3,1]\rightarrow[6,3,1]\rightarrow[6,2,1]\rightarrow[4,2,1]$。Output
**题目大意**：
给定一个整数 \( n \)。初始时，有一个从 0 开始编号、长度为 \( n \) 的环形序列 \( a \)，对于任意整数 \( i \)（\( 0 \leq i < n \)），满足 \( a_i = 2^i \)。任务是将序列 \( a \) 翻转，即使序列 \( a \) 满足对于任意整数 \( i \)（\( 0 \leq i < n \)），\( a_i = 2^{n-i-1} \) 成立。为此，你可以进行以下操作最多 \( 2.5 \times 10^5 \) 次：
- 选定整数 \( i \)，将 \( a_i \) 的值改为 \( a_i \text{ xor } a_{(i+1) \bmod n} \)。其中 \( \text{xor} \) 表示按位异或运算。
题目保证在给定的限制下一定有解。你需要找出任意一组满足要求的解。
**输入格式**：
输入一行一个整数 \( n \)（\( 2 \leq n \leq 400 \)）。
**输出格式**：
首先输出一行一个整数 \( k \)（\( 0 \leq k \leq 2.5 \times 10^5 \)）表示你所构造的操作方案的操作次数。接下来输出一行 \( k \) 个整数表示你每次操作所选择的 \( i \)（\( 1 \leq i \leq n \)）。你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。
**样例解释**：
- 对于样例一：
- 初始 \( a \) 为 \( [1,2] \)。
- 第一次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [1,3] \)。
- 第二次操作选择 \( i=0 \)，操作后 \( a \) 为 \( [2,3] \)。
- 第三次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [2,1] \)，此时目标达成。
- 对于样例二：
- 下面展示了样例输出对应的流程：
\( [1,2,4] \rightarrow [1,6,4] \rightarrow [7,6,4] \rightarrow [7,2,4] \rightarrow [5,2,4] \rightarrow [5,2,1] \rightarrow [5,3,1] \rightarrow [6,3,1] \rightarrow [6,2,1] \rightarrow [4,2,1] \)。
**题目描述（英文）**：
You have an array \( a_0, a_1, \ldots, a_{n-1} \) of length \( n \). Initially, \( a_i = 2^i \) for all \( 0 \le i < n \). Note that array \( a \) is zero-indexed.
You want to reverse this array (that is, make \( a_i \) equal to \( 2^{n-1-i} \) for all \( 0 \le i < n \)). To do this, you can perform the following operation no more than \( 250,000 \) times:
- Select an integer \( i \) (\( 0 \le i < n \)) and replace \( a_i \) by \( a_i \oplus a_{(i+1) \bmod n} \).
Here, \( \oplus \) denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
Your task is to find any sequence of**题目大意**： 给定一个整数 \( n \)。初始时，有一个从 0 开始编号、长度为 \( n \) 的环形序列 \( a \)，对于任意整数 \( i \)（\( 0 \leq i < n \)），满足 \( a_i = 2^i \)。任务是将序列 \( a \) 翻转，即使序列 \( a \) 满足对于任意整数 \( i \)（\( 0 \leq i < n \)），\( a_i = 2^{n-i-1} \) 成立。为此，你可以进行以下操作最多 \( 2.5 \times 10^5 \) 次： - 选定整数 \( i \)，将 \( a_i \) 的值改为 \( a_i \text{ xor } a_{(i+1) \bmod n} \)。其中 \( \text{xor} \) 表示按位异或运算。 题目保证在给定的限制下一定有解。你需要找出任意一组满足要求的解。 **输入格式**： 输入一行一个整数 \( n \)（\( 2 \leq n \leq 400 \)）。 **输出格式**： 首先输出一行一个整数 \( k \)（\( 0 \leq k \leq 2.5 \times 10^5 \)）表示你所构造的操作方案的操作次数。接下来输出一行 \( k \) 个整数表示你每次操作所选择的 \( i \)（\( 1 \leq i \leq n \)）。你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。 **样例解释**： - 对于样例一： - 初始 \( a \) 为 \( [1,2] \)。 - 第一次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [1,3] \)。 - 第二次操作选择 \( i=0 \)，操作后 \( a \) 为 \( [2,3] \)。 - 第三次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [2,1] \)，此时目标达成。 - 对于样例二： - 下面展示了样例输出对应的流程： \( [1,2,4] \rightarrow [1,6,4] \rightarrow [7,6,4] \rightarrow [7,2,4] \rightarrow [5,2,4] \rightarrow [5,2,1] \rightarrow [5,3,1] \rightarrow [6,3,1] \rightarrow [6,2,1] \rightarrow [4,2,1] \)。 **题目描述（英文）**： You have an array \( a_0, a_1, \ldots, a_{n-1} \) of length \( n \). Initially, \( a_i = 2^i \) for all \( 0 \le i < n \). Note that array \( a \) is zero-indexed. You want to reverse this array (that is, make \( a_i \) equal to \( 2^{n-1-i} \) for all \( 0 \le i < n \)). To do this, you can perform the following operation no more than \( 250,000 \) times: - Select an integer \( i \) (\( 0 \le i < n \)) and replace \( a_i \) by \( a_i \oplus a_{(i+1) \bmod n} \). Here, \( \oplus \) denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Your task is to find any sequence of
给定一个整数 \( n \)。初始时，有一个从 0 开始编号、长度为 \( n \) 的环形序列 \( a \)，对于任意整数 \( i \)（\( 0 \leq i < n \)），满足 \( a_i = 2^i \)。任务是将序列 \( a \) 翻转，即使序列 \( a \) 满足对于任意整数 \( i \)（\( 0 \leq i < n \)），\( a_i = 2^{n-i-1} \) 成立。为此，你可以进行以下操作最多 \( 2.5 \times 10^5 \) 次：
- 选定整数 \( i \)，将 \( a_i \) 的值改为 \( a_i \text{ xor } a_{(i+1) \bmod n} \)。其中 \( \text{xor} \) 表示按位异或运算。
题目保证在给定的限制下一定有解。你需要找出任意一组满足要求的解。
**输入格式**：
输入一行一个整数 \( n \)（\( 2 \leq n \leq 400 \)）。
**输出格式**：
首先输出一行一个整数 \( k \)（\( 0 \leq k \leq 2.5 \times 10^5 \)）表示你所构造的操作方案的操作次数。接下来输出一行 \( k \) 个整数表示你每次操作所选择的 \( i \)（\( 1 \leq i \leq n \)）。你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。
**样例解释**：
- 对于样例一：
- 初始 \( a \) 为 \( [1,2] \)。
- 第一次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [1,3] \)。
- 第二次操作选择 \( i=0 \)，操作后 \( a \) 为 \( [2,3] \)。
- 第三次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [2,1] \)，此时目标达成。
- 对于样例二：
- 下面展示了样例输出对应的流程：
\( [1,2,4] \rightarrow [1,6,4] \rightarrow [7,6,4] \rightarrow [7,2,4] \rightarrow [5,2,4] \rightarrow [5,2,1] \rightarrow [5,3,1] \rightarrow [6,3,1] \rightarrow [6,2,1] \rightarrow [4,2,1] \)。
**题目描述（英文）**：
You have an array \( a_0, a_1, \ldots, a_{n-1} \) of length \( n \). Initially, \( a_i = 2^i \) for all \( 0 \le i < n \). Note that array \( a \) is zero-indexed.
You want to reverse this array (that is, make \( a_i \) equal to \( 2^{n-1-i} \) for all \( 0 \le i < n \)). To do this, you can perform the following operation no more than \( 250,000 \) times:
- Select an integer \( i \) (\( 0 \le i < n \)) and replace \( a_i \) by \( a_i \oplus a_{(i+1) \bmod n} \).
Here, \( \oplus \) denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
Your task is to find any sequence of**题目大意**： 给定一个整数 \( n \)。初始时，有一个从 0 开始编号、长度为 \( n \) 的环形序列 \( a \)，对于任意整数 \( i \)（\( 0 \leq i < n \)），满足 \( a_i = 2^i \)。任务是将序列 \( a \) 翻转，即使序列 \( a \) 满足对于任意整数 \( i \)（\( 0 \leq i < n \)），\( a_i = 2^{n-i-1} \) 成立。为此，你可以进行以下操作最多 \( 2.5 \times 10^5 \) 次： - 选定整数 \( i \)，将 \( a_i \) 的值改为 \( a_i \text{ xor } a_{(i+1) \bmod n} \)。其中 \( \text{xor} \) 表示按位异或运算。 题目保证在给定的限制下一定有解。你需要找出任意一组满足要求的解。 **输入格式**： 输入一行一个整数 \( n \)（\( 2 \leq n \leq 400 \)）。 **输出格式**： 首先输出一行一个整数 \( k \)（\( 0 \leq k \leq 2.5 \times 10^5 \)）表示你所构造的操作方案的操作次数。接下来输出一行 \( k \) 个整数表示你每次操作所选择的 \( i \)（\( 1 \leq i \leq n \)）。你并不需要最小化操作次数，只需构造任意一组满足要求的操作方案即可。 **样例解释**： - 对于样例一： - 初始 \( a \) 为 \( [1,2] \)。 - 第一次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [1,3] \)。 - 第二次操作选择 \( i=0 \)，操作后 \( a \) 为 \( [2,3] \)。 - 第三次操作选择 \( i=1 \)，操作后 \( a \) 为 \( [2,1] \)，此时目标达成。 - 对于样例二： - 下面展示了样例输出对应的流程： \( [1,2,4] \rightarrow [1,6,4] \rightarrow [7,6,4] \rightarrow [7,2,4] \rightarrow [5,2,4] \rightarrow [5,2,1] \rightarrow [5,3,1] \rightarrow [6,3,1] \rightarrow [6,2,1] \rightarrow [4,2,1] \)。 **题目描述（英文）**： You have an array \( a_0, a_1, \ldots, a_{n-1} \) of length \( n \). Initially, \( a_i = 2^i \) for all \( 0 \le i < n \). Note that array \( a \) is zero-indexed. You want to reverse this array (that is, make \( a_i \) equal to \( 2^{n-1-i} \) for all \( 0 \le i < n \)). To do this, you can perform the following operation no more than \( 250,000 \) times: - Select an integer \( i \) (\( 0 \le i < n \)) and replace \( a_i \) by \( a_i \oplus a_{(i+1) \bmod n} \). Here, \( \oplus \) denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Your task is to find any sequence of