問題一覧 > 通常問題

No.3223 K-XOR Increasing Sequence

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : nauclhlt / テスター : Cafe1942
お気に入りにしたユーザー ProblemId : 12450 / 自分の提出
問題文最終更新日: 2025-08-01 23:42:08
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 476 (順位表) の他の問題:

Problem Statement

You are given positive integers $N, K$. Here, $N>K$.

Consider a sequence of non-negative integers $A=(A_1, A_2, \cdots, A_N)$ of length $N$. We say that $A$ is a good sequence if and only if it satisfies all of the following conditions.

  • All values contained in $A$ are less than $2^{20}$
  • For every integer $i$ satisfying $K+1\leq i\leq N$, $A_{i-K}\oplus A_{i-K+1}\oplus \cdots \oplus A_{i-1} < A_i$

Determine whether there exists a good sequence $A$ satisfying $A_1=X$ and $A_N=Y$, and if one exists, output one such sequence.

Here, for non-negative integers $P, Q$, $P\oplus Q$ denotes the bitwise XOR of $P$ and $Q$.

Input

$N\ K\ X\ Y$
  • $2\leq N\leq 10^6$
  • $1\leq K\lt N$
  • $0\leq X, Y<2^{20}$
  • All input values are integers

Output

On the $1$ line, output Yes if a good sequence exists, and No otherwise.

If the answer is Yes, output on the $2$ line an example of a good sequence $A=(A_1, A_2, \cdots, A_N)$ satisfying the conditions, in the following format. (If there are multiple, you may output any of them.)

$A_1\ A_2\ \cdots\ A_N$

Print a newline at the end.

Sample

Sample 1
Input
3 2 2 6
Output
Yes
2 1 6

$A=(2, 1, 6)$ indeed satisfies the conditions, since $A_1=2=X, A_N=6=Y, A_1\oplus A_2<A_3$.

Note that many other good sequences satisfying the conditions exist, such as $A=(2, 0, 6)$ and $ A=(2, 7, 6)$.

Sample 2
Input
10 3 7 13
Output
Yes
7 4 1 3 7 8 13 3 7 13
Sample 3
Input
2 1 100 1
Output
No

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