「Stoi2033」世界未末日

ID: 4608

远端评测题

1000ms

128MiB

难度: 5

上传者:

标签>

递推

博弈论

二分

O2优化

题目背景

注意：利用提交反馈以套取数据的行为属于作弊。

就算是世界要崩溃
亲爱的我也绝不会落泪
不放弃爱过的那种感觉
珍惜着有你记忆的一切
就算是世界要倾斜
亲爱的我也绝不说离别
尽管末日威胁再强烈
有爱就不累
——《世界未末日》

Vinsta 和 Stella 有 $n$ 堆石子，第 $i$ 堆有 $s_i$ 个。

她们约定从 Vinsta 开始轮流操作，每次操作可以选择不少于 $1$ 堆且不超过 $k$ 堆的石子。对于第 $i$ 堆石子，可以选取两个实数 $a,b$ 满足：

并丢掉第 $i$ 堆的 $c$ 个石子，即 $s_i\leftarrow s_i-c$ 。不能操作者败，她们想要知道 Vinsta 是否有必胜策略。

第一行共三个正整数： $n,k,S$ ，其中 $S=\max\{s_i\}$ 。

第二行共 $n$ 个正整数： $s_i$ ，表示初始时第 $i$ 堆的石子个数。

输出共一行。有必胜策略输出 YES，否则输出 NO。

7 1 13
2 3 4 5 7 10 11

YES

8 1 13
2 3 4 5 7 10 11 13

NO

7 2 100
19 26 8 17 11 45 14

YES

本题采用捆绑测试。

Subtask	$1\le n \le$	$1\le S \le$	分值
$1$	$300$	$300$	$7$
$2$		$3 \times 10^7$	$8$
$3$		$3\times 10^{10}$	$16$
$4$	$3\times 10^6$	$3$	$3$
$5$		$3 \times 10^3$	$3$
$6$		$3 \times 10^7$	$16$
$7$		$3\times 10^{10}$	$47$

对于 $100\%$ 的数据， $1 \le k \le n \le 3 \times 10^6$ ， $1 \le S \le 3 \times 10^{10}$ 。