A15552. Circular Xor Reversal
编程题
普及/提高-
知识点
题目描述
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.
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.
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]$ .
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]$ .