# 111 選手班 - 數學
###### tags: `宜中資訊` `CP`
2022.08.23

[109 slide](https://hackmd.io/@Ccucumber12/r19FPNMiI#/)
[110 slide](https://hackmd.io/@Ccucumber12/Hy8nj-fxt#/)

## Outline
- 模運算
- 基本運算
- 費馬小定理
- 模逆元
- 數論
- 質數
- 擴展歐幾里得算法
- 一次同餘方程
- 矩陣
- 基本運算
- 矩陣快速冪
- Nim

## Nim
### 題目
有 $N$ 堆石頭，其中第 $i$ 堆有 $a_i$ 顆石頭。兩個玩家輪由操作，每次可以選擇任意一堆拿走任意正整數顆石頭。最後無法操作（沒有石頭可以取）的玩家落敗。給定起始狀態，若兩方皆以最佳策略遊玩，請問先手還是後手贏？

### 簡化題目
- 剩 $1$ 堆：先手贏，直接拿走
- 剩 $2$ 堆
- 兩堆數量相同：後手贏，模仿前者動作
- 兩堆數量不同：先手贏，取成兩堆相同

### 圖論觀點
- 有向無環圖
- 必勝狀況 $\to$ 全部都是必輸狀況
- 必輸狀況 $\to$ 至少一個必勝狀況

### XOR
令 $t = a_1 \oplus a_2 \oplus \cdots \oplus a_n$
- 終點：所有石頭皆空 $t = 0$
- 前一步：至少有一堆石頭 $t \neq 0$

**引理一**
若 $t = 0$ 則下一步 $t' \neq 0$

**引理二**
若 $t \neq 0$ 則下一步有可能 $t' = 0$

定理：先手獲勝若且唯若 $t \neq 0$
其中 $t$ 又被稱作 nim 的**特徵值**

## 題單
[contest](https://vjudge.net/contest/511866)
password：`111apcs`