問題一覧 > 通常問題

No.3223 K-XOR Increasing Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 17
作問者 : Nauclhlt🪷 / テスター : Cafe1942
ProblemId : 12450 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-08-01 23:42:08

問題文

正整数 $N, K$ が与えられます。ここで $N>K$ です。

長さ $N$ の非負整数列 $A=(A_1, A_2, \cdots, A_N)$ が次の条件をすべて満たすとき、またそのときに限って $A$ は良い数列であるといいます。

  • $A$ に含まれる値はすべて $2^{20}$ 未満である
  • $K+1\leq i\leq N$ を満たす任意の整数 $i$ に対して、$A_{i-K}\oplus A_{i-K+1}\oplus \cdots \oplus A_{i-1} < A_i$

良い数列 $A$ であって、$A_1=X$ かつ $A_N=Y$ を満たすようなものが存在するか判定し、存在するならひとつ出力してください。

ここで、非負整数 $P, Q$ に対して $P\oplus Q$ で $P$ と $Q$ のビットごとのXORを表します。

入力

$N\ K\ X\ Y$
  • $2\leq N\leq 10^6$
  • $1\leq K\lt N$
  • $0\leq X, Y<2^{20}$
  • 入力はすべて整数

出力

良い数列が存在するなら Yes、そうでないなら No を $1$ 行目に出力してください。

もし答えが Yes であれば、条件を満たす良い数列 $A=(A_1, A_2, \cdots, A_N)$ の一例を $2$ 行目に次の形式で出力してください。(複数あればどれを出力してもよいです)

$A_1\ A_2\ \cdots\ A_N$

最後に改行してください。

サンプル

サンプル1
入力
3 2 2 6
出力
Yes
2 1 6

$A=(2, 1, 6)$ は $A_1=2=X, A_N=6=Y, A_1\oplus A_2<A_3$ より確かに条件を満たします。

なお、他にも $A=(2, 0, 6)$ や $ A=(2, 7, 6)$ など条件を満たす良い数列はいくつも存在することに注意してください。

サンプル2
入力
10 3 7 13
出力
Yes
7 4 1 3 7 8 13 3 7 13
サンプル3
入力
2 1 100 1
出力
No

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