P7490 「Stoi2031」蒲公英的约定（vol.1）

题目背景

一起长大的约定那样清晰拉过勾的我相信说好要一起旅行是你如今唯一坚持的任性

——《蒲公英的约定》

题目描述

清和如在玩游戏。她们有 $n$ 丛蒲公英，每丛分别有 $s_{i}$ 朵。这些蒲公英有一个神奇的性质：有一个给定的常数 $σ \in (0, 1)$ ， $x$ 朵蒲公英会分出 $⌊ σ x ⌋$ 朵为一组，剩下 $x - ⌊ σ x ⌋$ 朵继续分组，直到分出的组没有蒲公英即 $⌊ σ x ⌋ = 0$ 为止。她们称这种现象为任性。现在她们的每丛蒲公英都有任性的现象。她们的游戏规则如下：从清开始，两人轮流进行旅行。一次旅行为选择一丛蒲公英并吹散这一丛的第一组中的若干朵蒲公英，至少要吹一朵，至多吹的朵数为第一组的朵数，即不能吹散除第一组外的蒲公英。当第一组为空时，其下一组成为第一组。若这一丛只剩下一组蒲公英，这一丛不能再被选定。每丛蒲公英都不能被选定时，游戏结束，当前轮到的人落败。她们想知道如果清第一次旅行时等概率选择其中一丛可吹散的蒲公英再等概率选择吹散的朵数后两人都按最优策略操作，那么清的胜率 $x mod 20190816170251$ 的值将会是多少。

与 vol.2 的区别是，蒲公英在被吹散一部分后不会重新分组。

输入格式

第一行两个正整数 $i d, n$ ，其中 $i d$ 表示 Subtask 编号。

第二行 $n$ 个正整数，第 $i$ 个表示 $s_{i}$ 。

若 $i d > 3$ ，第三行输入两个正整数 $p, q$ 表示 $σ = \frac{p}{q}$ 。

输出格式

一行一个整数，表示清的胜率 $x mod 20190816170251$ 。

输入输出样例 #1

输入 #1

1
2
3

4 3
1 1 1
1 6

输出 #1

输入输出样例 #2

输入 #2

1
2
3

6 3
1 7 3
1 3

输出 #2

1	`5047704042563`

说明/提示

简述版题意：

有 $n$ 丛蒲公英，第 $i$ 丛有 $s_{i}$ 朵。给定实数 $σ$ ，每丛会分为若干组，第 $j$ 组有 $t_{j}$ 朵，且满足 $t_{j} = ⌊ σ (s_{i} - \sum_{k = 1}^{j - 1} t_{k}) ⌋$ ，当 $t_{j} = 0$ 时不再分组。两人轮流操作，每次操作可以选择一丛蒲公英，并选择一个整数 $c \in t_{j}$ ，从这丛蒲公英中吹散 $c$ 朵，将 $t_{j}$ 变为 $t_{j} - c$ ，其中 $j$ 为操作之前这丛蒲公英中满足 $t_{j} \neq 0$ 的最小正整数。必须至少吹一朵，不能操作者败。求先手第一步等概率选择任意一丛可操作的蒲公英再等概率选择吹散的朵数后两人都采取最优策略时先手的胜率 $x mod 20190816170251$ 的值。

样例解释：

对于样例 $1$ ，清无法操作，胜率为 $0$ 。

对于样例 $2$ ，初始局面为 $\set0;1},\set2,1,1,1,0;2},\set1,0;2}$ ，清可以选择第 $2$ 丛并在两种操作中选择吹散 $2$ 朵变成 $\set0;1},\set1,1,1,0;2},\set1,0;2}$ ，选择第 $3$ 丛没有可取胜的策略，且第 $1$ 丛不能选择，总胜率为 $\frac{\frac{1}{2} + 0}{2} = \frac{1}{4}$ 。

数据范围：

本题采用捆绑测试，各个 Subtask 的分数与限制如下。

Subtask No.	$n \leq$	$s_{i} \leq$	$σ$ 限制	分值
$1$	$3 \times 10^{5}$	$10^{10}$	$σ = \frac{\sqrt{2} + 1}{3}$	$10$
$2$	$3 \times 10^{5}$	$10^{10}$	$σ = \frac{\sqrt{3} + 1}{5}$	$10$
$3$	$3 \times 10^{5}$	$10^{10}$	$σ = \frac{\sqrt{5} - 1}{2}$	$10$
$4$	$100$	$1$	无	$3$
$5$	$100$	$100$	$σ = \frac{1}{2}$	$7$
$6$	$100$	$10^{6}$	无	$13$
$7$	$3 \times 10^{5}$	$10^{10}$	$σ \geq \frac{1}{2}$	$47$

对于 $100 %$ 的数据， $1 \leq n \leq 3 \times 10^{5}, 1 \leq s_{i} \leq 10^{10}, 1 \leq p < q \leq 10^{9}$ 。

本题读入量较大，可以选择使用比赛描述中的快速读入模板以加快读入速度。

题解

显然每丛蒲公英是一个独立的 ICG 游戏。

我们用 $[a_{1}]$ 表示只有一组的一丛，这一丛不能被选中，其 SG 函数为

SG (⟨ a_{1} ⟩) = 0

对于一丛两组蒲公英 $[a_{1}, a_{2}]$ ，其 SG 函数为

SG (⟨ a_{1}, a_{2} ⟩) = a_{1}

对于多组的一丛，分组为 $[a_{1}, a_{2}, \dots, a_{n}]$ ，其 SG 函数为

SG (⟨ a_{1}, a_{2}, \dots, a_{n} ⟩) = {\begin{cases} a_{1} if a_{1} > SG (⟨ a_{2}, a_{3}, \dots, a_{n} ⟩) \\ a_{1} - 1 else \end{cases}

考虑到 $a_{1} \geq a_{2}$ 且 $SG (⟨ a_{2}, a_{3}, \dots, a_{n} ⟩) \leq a_{2}$ ，因此上式中 $SG (⟨ a_{1}, a_{2}, \dots, a_{n} ⟩) = a_{1} - 1$ 当且仅当 $a_{1} = a_{2} = SG (⟨ a_{2}, a_{3}, \dots, a_{n} ⟩)$ 。

根据这一性质可以 $O (1)$ 求出 $SG (x)$ ，其中 $x$ 为一丛蒲公英的总数。

TODO：显然 $x$ 及其后继状态 SG 值取遍 $0, 1, \dots, ⌊ σ x ⌋$ 且互不重复。因此只要对于最终整个游戏的 SG 值 $a n s$ 满足 $SG (x) xor a n s \leq ⌊ σ x ⌋$ 则将答案加上 $\frac{1}{n ⌊ σ x ⌋}$ 。