J - Clover
Ceylon
4
s
1024
MB
100
点
問題文
$N$ 本のクローバーがあります。各クローバーの葉の枚数は $M$ 種類の数字 $A _ 1 , A _ 2, \ldots A _ M$ 枚のいずれかです。$N$ 本のクローバーについて、葉の枚数の総 xor をとったものが $K$ となることがあり得るか判定してください。
$T$ 個のテストケースが与えられるため、それぞれ回答してください。
制約
- $1 \leq T \leq 50$
- $1 \leq N \leq 10^{18}$
- $1 \leq M \leq 100$
- $0 \leq K \leq 2 \times 10^5$
- $0 \leq A _ 1\lt A _ 2 \lt \cdots \lt A _ M \leq 2 \times 10^5$
- 全てのケースの $M$ の総和は $100$ を超えない。
- 入力はすべて整数
入力
$T$
$\mathrm{case} _ 1$
$\mathrm{case} _ 2$
$\vdots$
$\mathrm{case} _ T$
各テストケースは以下の形式で与えられる。
$N$ $M$ $K$
$A _ 1$ $A _ 2$ $\ldots$ $A _ M$
出力
$T$ 行出力せよ。 $i$ 行目には、 $i$ 番目のテストケースについて総 xor が $K$ となることがあり得る場合 Yes を、ありえない場合は No を出力せよ。
入力例 1
4
5 3 3
2 3 4
2 3 5
2 3 4
10 3 7
2 3 4
998244353 3 0
2 3 4
出力例 1
Yes
No
Yes
No
1つ目のテストケースについて、例えば5枚のクローバーの葉の枚数がそれぞれ $(2, 2, 3, 4, 4)$ のとき、葉の枚数の総 xor が $3$ となるため、Yes を出力します。
2つ目のテストケースについて、$(2, 3, 4)$ から $2$ 枚のクローバーの葉の枚数をどのように選んでも葉の枚数の総 xor を $5$ にすることはできないため No を出力します。
入力例 2
5
3 3 0
1 2 3
10 1 5
5
159 5 2
9 20 24 33 36
1 5 0
4 16 17 18 23
412550000040819879 23 111543
6503 8245 9149 11402 35420 48056 48165 53107 56069 74312 96205 109966 118174 118760 141729 142798 145892 167498 186248 188749 190590 195004 198284
出力例 2
Yes
No
No
No
Yes