No.3223 K-XOR Increasing Sequence
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt
Cafe1942