No.2881 Mod 2^N
タグ : / 解いたユーザー数 55
作問者 :
Iroha_3856
/ テスター :
Problem Statement
You are given a positive integer $N$.
Here, for $1 \leq i \leq N$, define the function $f_i(x)\ = (x \times 2^{i} + 1) \bmod 2^{N}$.
You are given non-negative integers $X, Y (0 \leq X, Y < 2^{N})$.
Consider a sequence $A = (A_1, A_2, \ldots, A_K)\ (1 \leq A_i \leq N)$ of length $K (0 \leq K \leq 10^6)$. For $i = 1, 2, \ldots, K$, perform the following,
- Operation: update $X$ to $f_{A_i}(X)$.
See the Output section for the detailed output format.
Input
$N\ X\ Y$
All inputs satisfy the following constraints.
- $1 \leq N \leq 60$
- $0 \leq X, Y < 2^{N}$
- All inputs are integers.
Output
If no $K, A$ described in the problem statement exist, output $-1$.
If they exist, output $K, A$ in the following format, followed by a newline at the end.Here, make sure that $0 \leq K \leq 10^{6}$ and $1 \leq A_i \leq N$ are satisfied.
$K$ $A_1\ A_2\ \ldots\ A_K$
Sample
Sample 1
Input
4 3 11
Output
2 2 1
Update $X = 3$ with $f_2(3) = (3 \times 2^2 + 1) \bmod 2^4 = 13$.
Update $X = 13$ with $f_1(13) = (13 \times 2^1 + 1) \bmod 2^4 = 11$.
Now $X = Y = 11$, so this is a correct answer.
Sample 2
Input
6 4 1
Output
1 6
Update $X = 4$ with $f_6(4) = (4 \times 2^6 + 1) \bmod 2^6 = 1$.
Now $X = Y = 1$, so this is a correct answer.
Output with $A_i > N$ is invalid, but output with $A_i = N$ is allowed.
Sample 3
Input
1 1 0
Output
-1
There is no way to make $X = Y$.
Sample 4
Input
5 3 3
Output
0
It is also allowed to perform no operations.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。