{"problem":{"name":"Increment or Xor","description":{"content":"You are given a positive integer $N$ and a sequence $A = (A_0, A_1, \\ldots, A_{2^N-1})$ of $2^N$ terms, where each $A_i$ is an integer between $0$ and $2^N-1$ (inclusive) and $A_i\\neq A_j$ holds if $i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc057_c"},"statements":[{"statement_type":"Markdown","content":"You are given a positive integer $N$ and a sequence $A = (A_0, A_1, \\ldots, A_{2^N-1})$ of $2^N$ terms, where each $A_i$ is an integer between $0$ and $2^N-1$ (inclusive) and $A_i\\neq A_j$ holds if $i\\neq j$.\nYou can perform the following two kinds of operations on $A$:\n\n*   Operation $+$: For every $i$, change $A_i$ to $(A_i + 1) \\bmod 2^N$.\n*   Operation $\\oplus$: Choose an integer $x$ between $0$ and $2^N-1$. For every $i$, change $A_i$ to $A_i\\oplus x$.\n\nHere, $\\oplus$ denotes bitwise $\\mathrm{XOR}$.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows:\n\n*   When $A \\oplus B$ is written in base two, the digit in the $2^k$'s place ($k \\geq 0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor example, we have $3 \\oplus 5 = 6$ (in base two: $011 \\oplus 101 = 110$).\n\n  \nYour objective is to make $A_i = i$ for every $i$. Determine whether it is achievable. It can be proved that, under the Constraints of this problem, one can achieve the objective with at most $10^6$ operations if it is achievable at all. Print such a sequence of operations.\n\n## Constraints\n\n*   $1\\leq N\\leq 18$\n*   $0\\leq A_i \\leq 2^N - 1$\n*   $A_i\\neq A_j$, if $i\\neq j$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_0$ $A_1$ $\\ldots$ $A_{2^N - 1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc057_c","tags":[],"sample_group":[["3\n5 0 3 6 1 4 7 2","Yes\n4\n-1 6 -1 1\n\nThe sequence of operations above changes the sequence $A$ as follows.\n\n*   Initially: $A = (5,0,3,6,1,4,7,2)$\n*   Operation $+$: $A = (6,1,4,7,2,5,0,3)$\n*   Operation $\\oplus$ ($x = 6$)：$A = (0,7,2,1,4,3,6,5)$\n*   Operation $+$: $A = (1,0,3,2,5,4,7,6)$\n*   Operation $\\oplus$ ($x = 1$)：$A = (0,1,2,3,4,5,6,7)$"],["3\n2 5 4 3 6 1 0 7","No\n\nNo sequence of operations achieves the objective."],["3\n0 1 2 3 4 5 6 7","Yes\n0\n\nPerforming zero operations achieves the objective. Whether an empty line is printed or not does not affect the verdict."]],"created_at":"2026-03-03 11:01:14"}}