---
tags: 全國模擬賽 2020
---
109 學年度普通型高級中等學校資訊學科能力競賽決賽 模擬賽 題解
===
### 題目連結
自然組：https://drive.google.com/file/d/1KAaPOYdzBuoC0hXdFwS5W0ZEItY61ktk/view
社會組：https://drive.google.com/file/d/1L-SLEkVPJryKrFpP6bHox1sq0o4rDC3k/view
## pA 蘋果與橘子 (Apple_Orange)
* author+setter: yp
### Subtask 1
`if else` $O(1)$。
### Subtask 2
$O(N^2)$ 枚舉。
### Subtask 3
將輸入的蘋果和橘子都和 $2$ 取餘數，因此會分成四種人。兩個人可以平分若且唯若他們是同一種。假設四種人分別有 $x_1,\dots,x_4$ 個人，則答案是 $\sum \binom{x_i}{2}$，$O(N)$。
## pA' 蘋果與橘子 EX (Apple_Orange_EX)
* author+setter: erd1
### Subtask 1
題目等價於求以下不定方程的正整數解個數。 $$ N = \sum_{i = 0}^3\binom{x_i}{2} = \frac{1}{2}\sum_{i = 0}^3{x_i}^2-x_i $$
可以做 $O(4N)$ 的 DP 得到解數。
### Subtask 2
此不定方程等價於 $$ 8N + 4 = \sum_{i = 0}^3 4{x_i}^2-4x_i+1 = \sum_{i = 0}^3 (2{x_i}-1)^2 $$
這等價於求 $8N+4$ 寫成四個正奇數的和的方法數。注意到$8N+4$如果是四個平方數的和，必定是四個偶數或四個奇數的平方(平方數模 $8$ 餘 $0$ 或 $1$ 或 $4$)。
故所有奇數解有 $r_4(8N+4)-r_4(2N+1)$ 個。因為每個變數都可以任意給定正負號，因此答案是 $\frac{1}{16}(r_4(8N+4)-r_4(2N+1))$ 。
根據雅可比四平方和定理，這會化簡成 $\sigma(2N+1)$。
枚舉因數可以 $O(\sqrt{N})$ 做完。
### Subtask 3
用個好一點的因式分解方法，例如暴力枚舉到 $O(\sqrt[3]{N})$ 再用 Pollard's rho 做完，或是 GNFS。
### Note
這題在 OEIS 有 QQ
----
## pB 典獄長與斯芬克斯 (Sphinx)
* author: tmwilliam
* setter: double
### Subtask 1
矩陣必定要形如 $\begin{bmatrix}k & -k \\ -k & k\end{bmatrix}$，用 `if` 判就好了，$O(1)$。
### Subtask 2
你可以將最後一行和最後一列以外的每個元素都 greedy 變成 $0$，然後判斷最後一行和最後一列是否全為 $0$ 即可。
### Extra
事實上每一行和每一列的總和在操作不變，所以你只要判斷每一行每一列的和是不是都是 $0$ 即可。這只需要 $O(N)$ 的額外記憶體。
## pB' 典獄長與斯芬克斯 EX (Sphinx_EX)
* author: toxicpie
* setter: double
首先注意到
1. $A$ 可以被消到 $B$ 若且唯若 $A$ 的每個直行的和等於 $B$ 的每個直行的和且 $A$ 的每個橫列的和等於 $B$ 的每個橫列的和。
2. 一定可以把他消到剩第一行和第一列。
2\. 告訴你 rank 至多是 $2$，而是否能做到 $rank = 0$ 是原題，因此我們只需要判斷答案是否為 $1$。
若矩陣$A$可以消到$B$使得 $\mathrm{rank}\ B = 1$，則 $$B_{ij}:B_{ik} = colsum_B[j] : colsum_B[k] = colsum_A[j] : colsum_A[k]$$
因此你知道 $B$ 的一整列兩兩元素之間的比。
因為第 $i$ 列的總和是 $rowsum_B[i] = rowsum_A[i]$，因此你可以算出 $B$ 的每個元素，亦即 $$B_{ij} = \frac{rowsum[i]\cdot colsum[j]}{S}$$
其中 $S$ 是每個元素的總和。
（當 $S = 0$，則每一項的分子必須也要有 $0$，亦即 $\forall i[rowsum[i] = 0]$ 或 $\forall i[colsum[i] = 0]$。此時只要把所有東西都消到剩第一行或第一列即可。）
因此你只要檢查對於所有 $i, j$，$rowsum[i]\cdot colsum[j] / S$ 是否是整數。如果是整數答案便為 $1$，否則答案為 $2$。
----
## pC 橢圓曲線 (Elliptic)
* author+setter: erd1
### Subtask 1 & 2
暴力枚舉 $O(p^2)$。
### Subtask 3
如題敘 $O(p\log p)$。
### Extra
預處理模逆元可以線性做到。給定 $x$ 時，會是一個 $y$ 的三次方程，因此要嘛至多 $3$ 個解，要嘛所有 $y$ 都是解。因此利用 bucket sort 也可以去掉最後排序的 $\log$。因此這可以做到 $O(p)$。
一些 random ramble
- 在題敘裡面已經很努力明示說要預處理模逆元了，沒有預處理時間大概會到兩倍。
原本想卡掉的最後被波路擋下來了。
- $p=2$ 的情況在各種地方會爛掉，例如配方乘以二的時候。把它分出來變單獨一個 subtask 就是為了讓你們看到你們到底錯在哪。
- 本來 $a = 0$ 的情況是沒有標在題本上的，範測也刻意避開了這個情形，想說這是這題唯一難的地方，但是還是被波路擋掉了。$a = 0, b\neq 0$ 時解是 $z = -cb^{-1}$，$a = b = 0, c\neq 0$ 時無解，$a = b = c = 0$時 $z$ 可以是任意餘數。
- 原本是出到 $p \leq 10^6$ 的，因為這個數字好看很多，並要求預處理以外都不能帶 $\log$。但是被黃克崴擋下來了才變這麼鬆的。
- 根據Extra的性質以上，答案最多有 $3N$ 筆。有一筆測資有出滿。我記得他是什麼$x(x+1)(x-1) \equiv 0\pmod p$，然後 $p$ 是最大的那個質數。
- 記得看小教室，我寫了好久。 我已經在五門課上看到橢圓函數的出現了，他應該是將數學的各個領域（分析、代數、幾何）結合應用的例子裡面最初等的例子了吧。我覺得很酷所以就丟上來了。另一個目的是為了模擬通篇廢話的閱讀素養題。
- 我們當初投票決定好要出一題閱讀素養題以後，原本要出 Tonelli-Shanks，可是又覺得它過於無聊，於是我就跑去翻 Computational Arithmetic Geometry ，就翻到 Schoof 的論文了。
## pC 橢圓曲線 EX (Elliptic_EX)
* author+setter: erd1
### Subtask 1
暴力枚舉 $O(p)$。
### Subtask 2
參見Schoof's algorithm。以下簡述做法。
$p = 2$ 或 $3$ 的情況一樣要分開處理。以下假設 $p > 3$。
注意到題目沒有保證輸入是橢圓曲線，因此我們要先檢查他的判別式。
若 $x^3+ax+b$ 的判別式 $\Delta = 4a^3+27b^2 = 0$，則他不是光滑的。
若$a = b = 0$，則$y^2=x^3 = (x^{-1}y)^6$。每個 $x^{-1}y\neq 0$都對到一組解，而$x = y = 0$也是一組解。總共 $p$ 組。
否則令$t = -3b(2a)^{-1}$，式子會變成 $y^2 = x^3-3t^2x+2t^3 = (x+2t)(x-t)^2$。注意到每個 $k = y(x-t)^{-1}$ 都可以對到一組解，除非此時 $k = \pm\sqrt{3t} \Rightarrow x = t$。另外還有 $x = t, y = 0$ 的那組。
因此若 $3t$ 模 $p$ 是平方數，則只有 $p-1$ 組解。否則是 $p+1$。
接著處理橢圓曲線的情形。眾所周知，橢圓曲線上的點形成一個群，而事實上這個群一定是兩個循環群的積（$E \simeq C_l\times C_m$, $m | l$）。根據 Hasse's theorem，若 $F_q$ 上的橢圓曲線有 $|E|$ 個點，則$\big||E| - (q+1)\big| \leq 2\sqrt{q}$。因此我們隨便抓一個曲線上的點 $P$，並對在那個區間中尋找滿足 $nP=0$ 的 $n$。如果只有一個 $n$ 我們就做完了。否則就挑另一個點再做一次。這是 $O(\sqrt{p}\log{p})$ 的，因為每次在曲線上做加法都要一個 $\log(p)$。
但前提是，這個隨機是好的。但好巧不巧他是爛的。如果你跟著維基百科做會TLE。
例如 $y^2 = x^3-x\pmod p$ 的群在 $p = 4n^2+1$ 的時候會同構於$C_n \times C_n$。因此每個點在那個區間都會有至少兩個 $n$ 滿足 $nP = 0$，因此你永遠戳不到一個好的點。這個例子是在 [這篇論文](https://www.mat.uniroma2.it/~schoof/exponentse.pdf) 找到的。
但是考慮曲線 $E':y^2 = x^3+g^2x+g^3b$，其中 $g$ 是任意一個非二次剩餘。這個曲線滿足 $|E| + |E'| = 2p+2$，而且你可以證明，如果 $p > 229$，則 $E'$ 或 $E'$ 上至少有一個點是好的。因為他是兩個循環群的積，所以事實上那條曲線上大多數的點都是好的(因為$n/\varphi(n) = O(n^\varepsilon)$)。
因此，你就只要在兩個曲線上交互戳點即可。複雜度 $O(\sqrt{p}\log{p})$。
以上沒有證明的東西應該都可以在 [這篇論文](http://www.numdam.org/article/JTNB_1995__7_1_219_0.pdf) 找到證明。
### Subtask 3
在那個區間做大步小步，可以做到 $O(\sqrt[4]{p}\log{p})$。
### Extra
另外，維基百科上面還有多項式時間的做法，例如 [SEA演算法](https://en.wikipedia.org/wiki/Schoof–Elkies–Atkin_algorithm) 是 $O(\log^4p)$ 的。但是我找得到的他的實作都是上千行的，所以應該不適合當題目（？
然後其實這題意外好寫，要是我早點發現他就會跑到自然組了（Ｘ
---
## pD 和尚端湯上塔堂 (Tower)
* author+setter: baluteshih
### Subtask 1
$O(N^2)$ 窮舉所有區間，每個區間 $O(N)$ 求最大值、最小值檢查。
共 $O(N^3)$
### Subtask 2
$O(N)$ 窮舉區間的左界，嘗試讓右界不斷遞增並同時維護最大和最小值，共 $O(N^2)$。
### Subtask 3
觀察到 $O(N^2)$ 的作法中，每個左界看到合法的最遠右界是非嚴格遞增的，因此可以使用雙指針維護，最大最小值則因為序列遞增能 $O(1)$ 得出。
$O(N)$。
### Subtask 4
使用雙指針並配合 multiset 或線段樹等可維護區間極值的資料結構控制全距。 $O(N\log N)$
### Extra
維護區間極值時可以使用兩個 deque 維護兩種單調隊列，如此一來可以將複雜度壓到 $O(N)$。
~~或用 $\langle O(N),O(1)\rangle$ RMQ~~
## pD' 和尚端湯上塔堂 EX (Tower_EX)
* author+setter: erd1
### Subtask 1
對每個詢問做一次原題 $O(NQ)$。
### Subtask 2
莫隊 $O(N\sqrt{Q}\log{N}+Q)$。可能有不帶 $\log$ 的做法可是我不在乎。
### Subtask 3
你可以算出在 $i$ 結束的區間最長可以從哪裡開始並稱他為$left[i]$。
則詢問 $l,r$ 的答案是 $$ \frac{(l+r+2)(r-l+1)}{2} - \sum_{i = l}^r \max(l, left[i])$$
將第二項拆解後可得 $$ \frac{(l+r+2)(r-l+1)}{2} - \sum_{i = l}^r [left[i]>l]\cdot left[i] - \sum_{i = l}^r[left[i]\le l]\cdot l$$
後兩項皆各為一個二維偏序問題，可以離線用 BIT 等資料結構完成 ~~（或吉如一）~~。總複雜度是 $O((N+Q)\log N)$。
---
## pE & pE' 量子糾纏 (Entanglement)
* author+setter: icube
### Subtask 1
不失一般性假設 $N \le M$：
如果 $N = 1$，輸出 $1$。
如果 $N = 2$，由於小 E 不停在兩個地點間往返，小 C 無法回頭，因此答案為 $M$。
如果 $N \ge 3$，輸出 $\texttt{INF}$。
### Subtask 2
和前一子題類似，但是當 $N = 2$，考慮 $H$ 是否有環。
如果 $H$ 有環，輸出 $\texttt{INF}$。
否則輸出 $H$ 上的最遠點對距離（樹直徑）。
### Subtask 3
假設 $G = (V_G, E_G), H = (V_H, E_H)$。
構造新圖 $Z = (V, E)$，其中 $V = \{(x, y) \mid 1 \le x \le N, 1 \le y \le M, g_x = h_y\}$ 且 $E = \{\{(x_1, y_1), (x_2, y_2)\} \mid (x_1, y_1) \in V, (x_2, y_2) \in V, \{x_1, x_2\} \in E_G, \{y_1, y_2\} \in E_H \}$。
$O((NM)^2)$ 枚舉 $x_1, y_1, x_2, y_2$ 建圖。
若 $Z$ 有環，答案為 $\texttt{INF}$。
否則對於每個連通塊計算樹直徑，輸出最大值。
樹直徑的計算可以使用平方時間的方法，不影響整體時間複雜度。
### Subtask 4
延續 Subtask 3。
對於所有 $1 \le c, d \le 2000$，紀錄 $G$ 裡有哪些 $\{u, v\}$ 的邊滿足 $g_u = c, g_v = d$。
枚舉 $H$ 的邊 $\{u, v\}$ 時直接查詢 $h_u, h_v$ 對應的邊，建圖時間化為 $O(N^2 + M^2 + |E|)$。
雖然 $|E|$ 的量級是 $O((NM)^2)$，但是當 $|E| \ge |V|$ 時必定有環，因此最終時間複雜度降為 $O(N^2 + M^2 + NM)$。
此子題的樹直徑須以線性時間計算，由於相關資料容易取得，於此不加贅述。
方便起見，以下假設 $N = M$。
Note 1: 此題建圖有 $O(N^3)$ 的做法，基本上無法通過測試。
Note 2: 假設 $\omega$-bit integer 的四則運算、位元運算和比較等等都是 $O(1)$，建圖有 $O(\frac{N^3}{\omega} + N^2\omega)$ 的做法，也能通過此題（提示： bitset）。
---
## pF 鬧鐘設置 (Alarm_clock)
* author+setter: HNO2
### Subtask 1
答案是 $\sum\limits_{i=2K+2}^{N} a_i + (2K+1)a_1$。
注意到一定要有一個鬧鐘設定響的時間是這個序列的最小值(也就是 $a_1$)， 而且很顯然這個鬧鐘只能由第 $K+1$ 個人設定。因此，前 $2K+1$ 個人起來的時間點只能是 $a_1$，便證明了上面那個答案的上界。
欲證明這個答案是下界也很簡單: 讓第 $K+1$ 個人設置鬧鐘在 $a_1$ 響，再對於 $K+2 \leq i \leq N-K$，設置一個鬧鐘在 $a_{i+K}$ 響起即可。
### Subtask 2
因為每個人來的時間點不是 $1$ 就是 $2$，因此相當於最小化 $a_i=2$ 但是起來時間點是 $1$ 的人。令序列 $b$ 為每個人最後起來的時間點，則不難發現: 在序列 $b$ 中，$b_i=1$ 的連續段長度至少要是 $2K+1$。這是因為，如果有一段連續段長度不足 $2K+1$，則沒有地方可以擺設鬧鐘。
則這個問題可以轉換為: 使用一些長度為 $2K+1$ 的區間覆蓋 $a$ ，且把所有 $1$ 都覆蓋的情況下，最少能覆蓋幾個 $2$。這個問題可以使用一個簡單的DP解決: 令 $dp_i$ 代表前 $i$ 個數字所有 $1$ 都覆蓋的情況下，最少能蓋到多少個 $2$。轉移如下:
\begin{cases}
dp_{i}=\min(dp_{i-1},\min\limits_{j \leq i-2K-1}(dp_j+sum[j+1,i]) & \text{if} \space a_i=2 \\
dp_{i}=\min\limits_{j \leq i-2K-1}(dp_j+sum[j+1,i]) & \text{if} \space a_i=1 \\
\end{cases}
其中 $sum[l,r]$ 代表 $[l,r]$ 區間中 $2$ 的個數。
### Subtask 3
考慮 $dp$ 狀態 $dp[L][R][i]$ 代表：把區間 $[L, R]$ 設好，並且指使用前 $i$ 小的數字的情況下，每個人可以睡覺的最大時間總和。
general 的轉移： $dp[L][R][i] = dp[L][R][i - 1]$ 。
此外，如果 $a[L], a[R]$ 比第 $i$ 個數字還大的話，還可以考慮轉移 $dp[L][R][i] = dp[L + 1][R][i] + v[i]$，$a[R]$ 的轉移類似。
除此之外，還要考慮轉移 $dp[L][R][i] = \max(dp[L][i'][i] + dp[i' + 1][R][i])$ 。
複雜度就是 $O(n^4)$
這是一個測題者寫出來很奇怪的解ww
### Subtask 4
有多種作法，以下只介紹其中一種。
令 $i$ 為序列 $a$ 中最小值的出現位置。則可以發現，至少要有一個鬧鐘覆蓋位置 $i$，設置時間在 $a_i$ 時間點響。假設這個鬧鐘設在位置 $j$ ，則由於每個鬧鐘影響範圍都一樣，且這個鬧鐘響起的時間是最早的，$j$ 左邊和右邊的鬧鐘不會互相干擾。
經由以上觀察，可以得到以下 DP 解: 令 $dp_l,r$ 代表在位置 $l,r$ 各設置一個鬧鐘的情況下，$[l,r]$ 這個區間的人最大的睡眠時間總和。若 $r-l+1 \leq 2K+2$ 則 $dp_{l,r}$ 為 $0$。否則，令 $i$ 為區間 $[l+1,r-1]$ 最小值發生點，轉移為 $dp_{l,r}=\max\limits_{\max(l+1,i-K) \leq j \leq \min(r-1,i+K)}(dp_{l,j}+dp_{j,r}+a_i \cdot (\min(r-K-1,j+K)-\max(l+K+1,j-K)))$。也就是算出左右兩邊的DP值後再計算這個鬧鐘可以讓多少人起來。時間複雜度 $O(N^2K)$。
## pF' 鬧鐘設置 EX (Alarm_clock_EX)
* author+setter: HNO2
### Subtask5
前面 4 個 Subtask 跟自然組一樣就不贅述了。
跳脫一下前面區間 DP 的想法。在 Subtask 2 中提到，在序列 $b$ 中，$b_i=1$ 的連續段長度至少要是 $2K+1$ 。在 General 的情況也有一個很類似的結論: 如果在序列 $b$ 區間 $[l,r]$ 數字都一樣，且滿足 $b_l < b_{l-1}, b_r<b_{r+1}$，則這個區間的長度至少為 $2K+1$。若稱這種區間為一個「長區間」，則會發現任意兩個長區間 $b$ 必為先遞增後遞減。
這樣子整個 DP 的雛型就出來了: 令 $dp_{i,j,k}$ 代表序列 $b$ 中，最後一個數字一樣的區間結尾在 $i$ ，他的值是 $j$ (需將輸入的數字先離散化)。$k$ 代表狀態: $k=0$ 代表前一個區間的數字比他大，$k=1$ 代表比他小，$k=2$ 代表他處在一個長區間的結尾。
轉移的話基本上只要注意「任意兩個長區間 $b$ 必為先遞增後遞減」，也就是除了 $k=1$ 不能轉 $k=0$ 以外其他都可以轉。轉移的時候可以使用前後綴 $\max$ 加速轉移，詳細轉移有些繁瑣就不附上來了。
最後答案是 $i=n,k=0 \vee k=2$ 的最大值。總時間複雜度是 $O(N^2)$ 。
### Extra
tmw 宣稱這題可以做到 $O(NK)$ 和 $O(N \log N)$，需要用到 CHT 線段樹等工具。只是因為我不會(X)就沒出進社會組了。
---
## pG 白銀柵欄 (Fence)
* author+setter: toxicpie
因為木製柵欄不用錢，所以我們可以直接讓他超長。以下用 $R(w, \theta)$ 來表示白銀柵欄長度為 $2w$，木製柵欄超長，且矩形重心的極角為 $\theta$ 的矩形。注意到蓋出 $R(w, \theta)$ 的花費是 $4w$。
### Subtask 1
可以發現若 $R(w, \theta)$ 同時包含 $(1, 0)$ 和 $(-1, 0)$，那 $\theta$ 一定是 $90^\circ$ 或 $270^\circ$。如果選擇 $\theta = 90^\circ$，那麼該矩形會蓋住所有 $y \ge 0$ 且 $|x| \le w$ 的點。因此答案是所有樹的 $x$ 座標絕對值中的最大者 $\times 4$。
時間複雜度： $O(n)$
### Subtask 2+3+4
#### 做法 1
固定 $w$ 的值，考慮 $R(w, \theta_0)$ 能蓋住 $(x, y)$ 時 $\theta_0$ 的條件：
- 若 $w \ge \sqrt{x^2 + y^2}$，那 $(x, y)$ 只要和矩形在白銀柵欄的同側就好，因此 $- \frac{\pi}{2} \le \theta_0 - \operatorname{atan2}(y, x) \le \frac{\pi}{2}$。
- 若 $w < \sqrt{x^2 + y^2}$，那麼除了前一項的條件，還要再滿足 $(0, 0)$ 和 $(x, y)$ 都在木製柵欄的同側。這等價於 $- \frac{\pi}{2} + \operatorname{acos}(\frac{w}{\sqrt{x^2 + y^2}}) \le \theta_0 - \operatorname{atan2}(y, x) \le \frac{\pi}{2} - \operatorname{acos}(\frac{w}{\sqrt{x^2 + y^2}})$。
也就是說，$\theta_0$ 的可能值一定是一個區間 (可以在腦中想像旋轉那個矩形，應該會很直觀 (?))。如果給定一個 $w$，那寬度 $w$ 的矩形能蓋住所有點若且唯若每棵樹對應的 $\theta_0$ 區間的交集非空，而這可以在 $O(n)$ 的時間內判斷。
因此，我們可以對答案二分搜。時間複雜度：$O(n\log(C))$，其中 $C = \epsilon^{-1}$ 且 $\epsilon$ 是允許的誤差。
#### 做法 2
做法 2 正確性的證明可能會需要 EX 版題解的某些 lemma ，但是在賽中應該不難猜出並相信結論是對的 (?)，並且實作拿到 AC。
假設不是所有點都在 $x$ 軸上。令 $R(w_m, \theta_m)$ 是一個最佳解，且 $\theta_l, \theta_r$ 分別是所有可行解 $R(w, \theta)$ 中，$\theta$ 的最小和最大值。可以想像 $\theta$ 連續的從 $\theta_l$ 轉到 $\theta_r$ 時都會有可行解，且對應的最小寬度在 $[\theta_l, \theta_m]$ 會遞減，而在 $[\theta_m, \theta_r]$ 會遞增。
因此，我們可以對 $\theta$ 做三分搜來找矩形寬度的最小值。時間複雜度： $O(n\log(C))$，其中 $C = \epsilon^{-1}$ 且 $\epsilon$ 是允許的誤差。
**注意：** 如果你寫了這兩種做法且常數很大 (像是使用了 `long double` 或是搜太多次)，那 Subtask 4 很有可能不會過。
## pG' 白銀柵欄 EX (Fence_EX)
* author+setter: toxicpie
小知識：這題的浮點數版本才是原本的 pG。
### Subtask 1
注意到 Subtask 1 等價於柵欄要圍住所有樹。觀察到有解若且唯若存在一條過原點的直線，使得所有樹都在他的同一側，所以極角排序後就可以簡單判斷有沒有解。
假設有解，且最佳解長這樣：
那麼，他一定會滿足這些條件：
1. $\overline{AD} \cup \overline{BC}$ 至少包含一棵樹。否則，我們可以縮小他的寬度，而矩形依然會包住所有樹，如下圖：
2. $\overline{OA} \cup \overline{AD}$ 至少包含一棵樹。否則，我們可以將矩形順時針旋轉並將寬度縮小，而依然會包住所有樹，如下圖：
3. $\overline{OB} \cup \overline{BC}$ 至少包含一棵樹，同 2.。
簡單的處理一下這些條件後，可以知道以下三點至少有一點會成立：
1. $\overline{OA}$ 上有一棵樹。
2. $\overline{OB}$ 上有一棵樹。
3. $\overline{AD}$ 上有一棵樹，且 $\overline{BC}$ 上有一棵樹。
因此可以分 case 找答案，取其中的最小值。
#### Case 1
若 $\overline{OA}$ 上有一棵樹，則答案為所有點的向量投影到 $\overline{AB}$ 上長度的最小值 $\times 4$，即 $$\max_{1 \le i \le n} \frac{\left|\overrightarrow{OP} \cdot (x_i, y_i)\right|}{\left|\overline{OP}\right|} \times 4$$
，其中 $P$ 是 $\overline{OA}$ 上的一棵樹。
而 $P$ 最直觀的找法，就是求原點到所有樹凸包的右切線。
#### Case 2
同上，答案為 $$\max_{1 \le i \le n} \frac{\left|\overrightarrow{OP} \cdot (x_i, y_i)\right|}{\left|\overline{OP}\right|} \times 4$$
，其中 $P$ 是原點到所有樹凸包的左切線 (他會在 $\overline{OB}$ 上)。
### Case 3
(這是實作較簡單的做法，其他做法如旋轉卡尺等也可以用。)
考慮所有樹對原點做對稱之後複製一份，如下圖：
可以發現，兩條木製柵欄分別為原本的樹和對稱後的樹的凸包切線，而答案即為原點到切線距離的 4 倍。不過，在更新答案之前，我們需要先檢查是否所有樹都在 $\overline{AB}$ 的同一側。
時間複雜度：
- 極角排序 $O(n\log(n))$
- Case 1 $O(n)$
- Case 2 $O(n)$
- Case 3 凸包 $+O(n) = O(n\log(n))$
總共為 $O(n\log(n))$ 。
### Subtask 2
其實作法同 Subtask 3 ，只是實作上會簡單不少。
### Subtask 3
我們需要找到一棵樹，使得砍掉他後，包住剩下的樹所需的矩形寬度會最小。有兩種情況：
1. 原本沒有解，但砍掉這棵樹後就有解了。發現到這種樹最多只有 4 個，而且可以通過極角排序簡單找出。一一嘗試砍掉他們並呼叫 Subtask 1 的解即可得到答案。
2. 原本的答案因為砍掉一棵樹後變小了。
由 subtask 1 的解法可以發現，砍掉一棵樹之後必須滿足以下其中一種，答案才有可能變小。
1. $\overline{AD} \cup \overline{BC}$ 上沒有樹。
2. $\overline{OA} \cup \overline{AD}$ 上沒有樹。
3. $\overline{OB} \cup \overline{BC}$ 上沒有樹。
再利用一次上面的性質，可以知道砍樹前的最佳解一定會是以下 case 的一種。
1. $\overline{AD} \cup \overline{BC}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。
2. $\overline{OA} \cup \overline{AD}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。
3. $\overline{OB} \cup \overline{BC}$ 恰有一棵樹。砍掉他後呼叫 Subtask 1 的解即可得到答案。
總時間複雜度一樣是 $O(n\log(n))$。
**Remark:** 為何所有輸出的 $q$ 都不會是 $10^9+7$ 的倍數呢？可以發現，以上所有 case 中算出的答案分母都是某兩個格子點之間的距離，也就是說，$q = x^2 + y^2$，其中 $x, y$ 是整數。由於 $-1$ 不是 $10^9+7$ 的二次剩餘，$x^2 + y^2 \equiv 0 \pmod{10^9+7}$ 只有在 $x \equiv y \equiv 0 \pmod{10^9+7}$ 才會滿足，而這在測資中不可能發生。
---
## pH & pH' 螞蟻捷運 (Ant_MRT)
* author+setter: tmwilliam
### Subtask 1
Floyd-Warshall + DP。
可以先對每個點對計算最小花費，之後再使用Floyd-Warshall。複雜度 $O(N^3)$ 但常數很小。
### Subtask 2
建圖
### Subtask 3
對於每一個節點$u$，計算$e_{i,j}=$用價格$2^i+j$最高可以達到的節點（$0\le i<17, -6<j<6$）。之後再用倍增算出最少需要多少花費才能抵達節點 $1$ 。
$O(((N+Q)C^2+M)\log N)$
### Subtask 4
對於每一個節點$u$，計算$e_i=$用價格$2^i$最高可以達到的節點（$0\le i<17$）。
對於每一個詢問$(u_i, v_i)$，一個詢問$(u_i, v_i)$可以分成$(u_i, w_i)$和$(v_i, w_i)$。我們可以計算最少要從$u$和$v$到LCA的價格為$c_u$和$c_v$。如果有路連通$c_u-1$和$c_v-1$，答案就是$c_u+c_v-1$。如果沒有，答案就是$c_u+c_v$。找路可以用2D區間和，或者可以可以在樹壓平用BIT維護:
* 每個節點 $v$ 在樹壓平以後可以對應一個區間 $[l_v,r_v]$ 。
* 對樹做一次DFS，對於每條路 $a_i,b_i$ ，在DFS到 $a_i$ 時，在另一端 $b_i$ 加1。
* 對於每個詢問 $(u,v)$ ，DFS到 $u$ 時紀錄 $[l_{v},r_{v}]$ 的總和。 在$u$ 的所有子樹DFS完以後，再詢問一次 $[l_{v},r_{v}]$ 。如果總和不一樣代表有路從 $u$ 到 $v$ 。
$O((N+Q+M)\log N)$
### Subtask 5
結合Subtask4和Subtask5。先對於每一個節點$u$，計算$e_{i,j}=$用價格$2^i+j$最高可以達到的節點（$0\le i<17, -6<j<6$）。之後可以發現對於每個點對 $u,v$ ，計算最少要從$u$和$v$到LCA的價格為$c_u$和$c_v$。之後需要找是否有權重 $k$ 的路連通 $u-k$ 與 $v-k$ ($1 \leq k \leq 5$)。找路一樣可以使用之前介紹的方法。
### Subtask 6
可以把三個數字塞進一個數字。
$O((NC^2+\frac{QC^3}{3}+M)\log N)$
### Note
這題的 Subtask 4 在 [CF](https://codeforces.com/problemset/problem/983/E) 上有，出出來以後就發現撞題了 QQ
Sign in with Wallet
Connect another wallet