该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

构造一个长度为 $N$ 的序列 $A$，满足每个元素的取值范围为 $1\le A_i\le 2^{30}$，并且序列中任意连续子序列的异或和均不等于 $0$，即

$$\forall\ 1\le i\le j\le N,\quad A_i\oplus A_{i+1}\oplus\cdots\oplus A_j \neq 0 .$$

如果存在多个满足条件的序列，你可以输出其中任意一个。

注：$\oplus$ 表示按位异或运算（XOR）。

输入格式

• 单行包含一个整数 $N$，表示要求构造序列的长度。

输出格式

• 输出 $N$ 个正整数，用空格分隔，表示序列 $A_1,A_2,\dots,A_N$。这些数必须满足题目中给出的约束（每个 $A_i$ 在 $[1,2^{30}]$ 且任意连续子段异或和不为 $0$）。

样例输入 1

4

样例输出 1（示例之一）

1 2 1 4

说明

样例解释

序列长度为 $4$，列出所有连续子段的异或可验证均不为 $0$（见原题例示）。

数据范围

对于 $100\%$ 的数据，

• $1\le N \le 10^{6}$。

各子任务限制：

测试点编号	$n \le$
$1\sim 3$	$30$
$4\sim 6$	$3000$
$7\sim 10$	$10^6$

校验器说明

题目提供了一个本地 checker（位于 xor 目录下，文件名示例 checker.exe），用于验证输出文件是否满足约束。校验器会检查如下内容：

• 输出是否有且仅有 $N$ 个整数；
• 每个数是否在区间 $[1,2^{30}]$；
• 是否存在某个连续子段的异或和为 $0$（若存在则判为错误）；

常见校验器提示：

• Open File Error：无法打开文件；
• Input N Error：读取输入文件失败；
• Input Element Not Enough：输出元素不足；
• Extra Elements：输出元素过多；
• Xor Zero Exists：存在异或为 $0$ 的连续子序列；
• Invalid Number：输出元素超出允许范围；
• Accept：通过校验。

注意：本地 checker 仅供本地调试使用，实际评测系统采用的校验器可能不同；你只需保证输出满足题目中给定的数学约束即可。

校验器下载

点击下载