問題一覧 > 通常問題

No.2881 Mod 2^N

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 45
作問者 : Iroha_3856Iroha_3856 / テスター : sortA0329sortA0329 tikuwa_tikuwa_ hiro1729hiro1729
3 ProblemId : 11042 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-08 08:24:10

問題文

正整数 $N$ が与えられます。

ここで、$1 \leq i \leq N$ について、関数 $f_i(x)\ = (x \times 2^{i} + 1) \bmod 2^{N}$ と定義します。

非負整数 $X, Y (0 \leq X, Y < 2^{N})$ が与えられます。

長さ $K (0 \leq K \leq 10^6)$ の列 $A = (A_1, A_2, \ldots, A_K)\ (1 \leq A_i \leq N)$ であって 、 $i = 1, 2, \ldots, K$ について、

  • 操作:$X$ を $f_{A_i}(X)$ に更新する。
と $K$ 回操作を行ったあと、$X = Y$ となるような $K, A$ があるか判定し、あるならそのような $K, A$ を出力してください。

詳しい出力形式は出力の欄を参照してください。

入力

$N\ X\ Y$

入力はすべて以下の制約を満たす

  • $1 \leq N \leq 60$
  • $0 \leq X, Y < 2^{N}$
  • 入力はすべて整数
$K$ は与えられないことに注意してください。

出力

もし問題文で説明される $K, A$ が存在しない場合、$-1$ を出力してください。

存在する場合、$K, A$ を以下の形式で出力し、最後に改行してください。
ここで、$0 \leq K \leq 10^{6}$ と $1 \leq A_i \leq N$ を満たすようにしてください。

$K$
$A_1\ A_2\ \ldots\ A_K$

サンプル

サンプル1
入力
4 3 11
出力
2
2 1

$X = 3$ を $f_2(3) = (3 \times 2^2 + 1) \bmod 2^4 = 13$ で更新します。

$X = 13$ を $f_1(13) = (13 \times 2^1 + 1) \bmod 2^4 = 11$ で更新します。

$X = Y = 11$ となったので、これで正解です。

サンプル2
入力
6 4 1
出力
1
6

$X = 4$ を $f_6(4) = (4 \times 2^6 + 1) \bmod 2^6 = 1$ で更新します。

$X = Y = 1$ となったので、これで正解です。

$A_i > N$ となる出力は不正ですが、$A_i = N$ となるような出力は許されています。

サンプル3
入力
1 1 0
出力
-1

$X = Y$ とするような方法はありません。

サンプル4
入力
5 3 3
出力
0

操作を行わないことも許されています。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。