No.2881 Mod 2^N
タグ : / 解いたユーザー数 41
作問者 :
Iroha_3856
/ テスター :
sortA0329
tikuwa_
hiro1729
問題文
正整数 $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)$ に更新する。
詳しい出力形式は出力の欄を参照してください。
入力
$N\ X\ Y$
入力はすべて以下の制約を満たす
- $1 \leq N \leq 60$
- $0 \leq X, Y < 2^{N}$
- 入力はすべて整数
出力
もし問題文で説明される $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もしくは右上の雲マークをクリックしてアカウントを作成してください。