F - Maximum Zero Xor Prefixes
Darjeeling
2
s
1024
MB
600
点
問題文
正の整数 $N$ が与えられます。$M=2^N-1$ とします。
$1,2,\ldots,M$ を並べ替えた順列 $P=(P_1,P_2,\ldots,P_M)$ を考えます。
各整数 $i$($1\leq i\leq M$)について、
$Q_i=P_1\oplus P_2\oplus\cdots\oplus P_i$
と定めます。ここで、$\oplus$ は整数のビットごとの排他的論理和(XOR)を表します。
$Q_i=0$ を満たす $i$ の個数が最大となる順列 $P$ を1つ求めてください。
制約
- $2\leq N\leq18$
- 入力は整数である。
入力
入力は以下の形式で標準入力から与えられます。
$N$
出力
求めた順列 $P$ の要素を、以下の形式で空白区切りで 1 行に出力してください。
$P_1 \space P_2 \space \ldots \space P_M$
出力する整数は $1,2,\ldots,M$ をそれぞれちょうど 1 回ずつ含む必要があります。
条件を満たす順列が複数存在する場合は、どれを出力しても正解となります。
入力例 1
2
出力例 1
2 3 1
この出力では $Q=(2,1,0)$ となり、$Q_i=0$ を満たす $i$ の個数は1です。これが最大です。
他にも、$(1,3,2)$ などを出力しても、$Q = (1,2,0)$ で、 $Q_i = 0$ を満たす $i$ が1個で最大となり、正解となります。
入力例 2
3
出力例 2
4 1 6 3 7 2 5