問題一覧 > 通常問題

No.1228 I hate XOR Matching

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

Original Problem

XOR Matching
It is an interesting problem.

Problem Statement

If there exists an integer sequence $a = \{a_1,a_2,\dots , a_N\}$ satisfying the following conditions, construct $1$ such sequence.

  • $1 \le N \le 40$
  • $0 \le a_i < 2^{20}$
  • Each $i$ $(0 \le i < 2^{20})$ appears at most $2$ times in $a$
  • Among the $2^N-1$ non-empty subsequences of $a$, exactly $X$ have a bitwise XOR equal to $K$.

Constraints

  • All inputs are integers
  • $0 \le K < 2^{20}$
  • $0 \le X \le 10^9$

Input

$K\ X$

$K,X$ are given on $1$ line, separated by a space.

Output

Yes / No
$N$
$a_1\ a_2\ \dots\ a_N$

If no sequence satisfying the conditions exists, output No on $1$ line.
Otherwise, output Yes on $1$ line, and then output $2$ more lines.
On line $2$, output the length $N$ of the sequence, and on line $3$, output the sequence $a$ separated by spaces.
Finally, output a newline.

The verdict is undefined when the output does not follow the format specified above.

Sample

Sample 1
Input
3 2
Output
Yes
2
0 3

The subsequences of $a$ are $(0,3),(0),(3)$.
Among these, the subsequences whose $\mathrm{xor}$ is $3$ are $(0,3),(3)$, which is $2$ in total, so the conditions are satisfied.

Sample 2
Input
5 8
Output
Yes
4
5 0 0 5

There are $2$ occurrences of $(0,5)$.

Sample 3
Input
0 3
Output
Yes
3
0 1 1
Sample 4
Input
0 2
Output
No

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