← 返回题目列表

Codeforces · 1748/F

F. 循环异或反转

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

您有一个长度为 $$$n$$$ 的数组 $$$a_0, a_1, \ldots, a_{n-1}$$$。最初,对于所有 $$$0 \le i \lt n$$$,$$$a_i = 2^i$$$。请注意,数组 $$$a$$$ 是零索引的。

您想要反转此数组(即,对于所有 $$$0 \le i \lt n$$$,使 $$$a_i$$$ 等于 $$$2^{n-1-i}$$$)。为此,您可以执行以下操作不超过 $$$250\,000$$$ 次:

- 选择一个整数 $$$i$$$ ($$$0 \le i \lt n$$$) 并将 $$$a_i$$$ 替换为 $$$a_i \oplus a_{(i+1)\bmod n}$$$。

这里,$$$\oplus$$$ 表示按位异或运算。

你的任务是找到任何会导致数组 $$$a$$$ 被反转的操作序列。可以证明,在给定的约束条件下,总存在解。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 400$$$) — 数组 $$$a$$$ 的长度。

输出

在第一行打印一个整数 $$$k$$$ ($$$0 \le k \le 250\,000$$$) — 执行的操作数。

在第二行打印 $$$k$$$ 整数 $$$i_1,i_2,\ldots,i_k$$$ ($$$0 \le i_j \lt n$$$)。这里,$$$i_j$$$应该是在第$$$j$$$操作中选择的整数。

请注意,您不需要最小化操作数量。

示例

输入 #1

2

输出 #1

3
1 0 1

输入 #2

3

输出 #2

9
1 0 1 0 2 1 0 1 0

注意

在注释中,执行操作的元素被涂成红色。

在第一个测试用例中,数组 $$$a$$$ 将按以下方式更改:

$$$[1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]$$$。

在第二个测试用例中,数组 $$$a$$$ 将按以下方式更改:

$$$[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]$$$。