問題一覧 > 通常問題

No.2881 Mod 2^N

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 55
作問者 : Iroha_3856 / テスター : Rac tikuwa_ hiro1729
お気に入りにしたユーザー ProblemId : 11042 / 自分の提出
問題文最終更新日: 2024-09-08 08:24:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 445 (菁々祭プログラミングコンテスト2024) (順位表) の他の問題:

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)$.
Determine whether there exist $K, A$ such that $X = Y$ after performing the operation $K$ times in this way, and if they exist, output such $K, A$.

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.
Note that $K$ is not given.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。