# NPSC 2022 高中組初賽 pF 取蜜柑

## 題目

Alice 和 Bob 在玩 nim game。今天有 $n$ 堆石頭，第 $i$ 堆有 $a_i$ 顆石頭，雙方會按照以下方式取石頭：

1. 等機率選擇一堆非空的石頭
2. 自行決定要從該推移除幾顆，但至少要取一顆

取到最後一顆石頭的人獲勝，問雙方最佳策略下先手獲勝機率，模 $998244353$

### 範測

Input:
3
4
1 1 1 1
3
9 2 8
1
56562

Output:
0
499122177
1

=== 防雷 ===
=== 防雷 ===
=== 防雷 ===
=== 防雷 ===
=== 防雷 ===
=== 防雷 ===
=== 防雷 ===
=== 防雷 ===

## 答案

1. 若整個序列非 $1$ 的數量為 $0$，若 $n$ 是奇數則是 $1$，否則答案是 $0$。
2. 若整個序列非 $1$ 的數量至少為 $2$，則答案為 $\frac{1}{2}$
3. 否則令 $dp_n$ 為序列長度為 $n$ 且恰有一個非 $1$ 的答案，則可以推得：$dp_1 = 1, dp_n = \frac{1}{n} + \frac{n - 1}{n}(1 - dp_{n - 1})$

## 要怎麼想到

首先最暴力也在賽局題最常見的方法就是直接打表觀察，定義 $dp_{state}$ 為當前盤面為 $state$ 的先手獲勝機率，將所有小 case 輸出出來觀察後，發現一堆 $\frac{1}{2}$ 你差不多就快做完了

其他思考方向的話，首先看到範測只有 $0, 1, \frac{1}{2}$ 不免會懷疑是不是只有這三種可能，當你懷疑或傳完 WA 之後可能就會想到 $(1, 1, x), x > 1$ 是一種反例，這時稍微推廣一下會發現 $(1, 1, \ldots, 1, x), x > 1$ 會是一種獨立的 case，推導一下發現這種 case 的答案都 $\geq \frac{1}{2}$ 而且 $\frac{1}{2}$ 會交錯出現，這時就不難證明剩下的 case 都是 $\frac{1}{2}$ 了

## 證明

### part 1

首先先了解先手的最佳策略是什麼，而先手顯然是要到一個先手獲勝機率越小越好的狀態，才能提高自己的獲勝機率。

來開始討論上述答案討論的三種 case。首先 1. 的部分顯然是對的，3. 的部分由於當抽到非 $1$ 的那一堆時，先手方可以依照當前堆數的奇偶性決定要留一個或全部拿走來達到必勝的結果，所以可以推出上面的式子

而 2. 的部分，首先注意到 $dp_2 = \frac{1}{2}$，而當 $dp_n = \frac{1}{2}$，有：
$$
dp_{n + 2} = \frac{1}{n + 2} + \frac{n + 1}{n + 2}(1 - (\frac{1}{n + 1} + \frac{n}{n + 1}\times\frac{1}{2})) = \frac{1}{2}
$$

因此 $\forall n \geq 1, dp_n \geq \frac{1}{2}$ 成立。

### part 2

之後定義 $f(n, a, b)$ 代表有 $n$ 堆石頭，其中有 $n - 2$ 堆是 $1$，剩下一堆是 $a$ 一堆是 $b$ 先手獲勝的機率。

考慮數歸，我們想先證明 $\forall n \geq 2, f(n, 2, 2) = \frac{1}{2}$：

1. $n = 2$，暴力枚舉一下可以發現是 $\frac{1}{2}$

2. 假設 $f(k - 1, 2, 2) = \frac{1}{2}$，我們想要證明 $f(k, 2, 2) = \frac{1}{2}$。這裡分兩個 case：

(1) 抽到 $1$
(2) 抽到 $2$

對於 (1) 的話只能把他拿掉，所以獲勝機率會是 $1 - f(k - 1, a, b) = \frac{1}{2}$，(2) 的話由於 $dp_n \geq \frac{1}{2}$ 且 $dp_n$ 與 $dp_{n - 1}$ 有一個是 $\frac{1}{2}$，先手方將盤面弄到先手機率為 $\frac{1}{2}$ 的盤面一定最優，所以視奇偶性看要從該堆拿 $1$ 個或 $2$ 個即可，獲勝機率依然會是$\frac{1}{2}$

因此由數歸可以得知上述的 claim 是對的。

### part 3

接著我們想證明 $\forall n, a, b \geq 2, f(n, a, b) = \frac{1}{2}$：

1. $n \geq 2, a = 2, b = 2$，上面證完了

2. 假設 $\forall 2 \leq k \leq n, 2 \leq x \leq a, 2 \leq y \leq b, k + x + y < n + a + b, f(k, x, y) = \frac{1}{2}$ 皆成立，我們想要證明 $f(n, a, b) = \frac{1}{2}$。則考慮三個 case：

(1) 抽到 $1$
(2) 抽到 $a$
(3) 抽到 $b$

(1) 的話會變成 $f(n - 1, a, b) = \frac{1}{2}$，(2)(3) 的話可以發現所有能到達的狀態都 $\geq
\frac{1}{2}$，所以先手的策略依然是視奇偶性決定要拔到剩 $1$ 個或全拔。這樣答案依然為 $\frac{1}{2}$

由數歸證完前面的 claim 是好的

### part 4

上面我們已經證完非一個數為 $2$ 的情況都是 $\frac{1}{2}$，那 $> 2$ 的情況呢？

可以簡單發現一位玩家每次操作最多只能將非一的數量減少 $1$，所以若當前盤面有超過 $2$ 個非一的數，那他所有能到達的狀態顯然都是 $\frac{1}{2}$，所以也就證完了 case 2. 的正確性

## 後話

其實上面第 3 種 case 可以得出一個更單純也可能更乾淨的結論：
$$
dp_n = \frac{\lfloor\frac{n}{2}\rfloor}{n}
$$
賽中所有人都是直接用上面的式子算答案

此外，我們也可以得知雙方的最佳解永遠只會將石頭取光或取到剩一個，個人覺得蠻酷的XD