###### tags: `Editorial`
# HNO2 Contest for Code Community Editorial

:::success
想要補題可以點原競賽連結進去，或者是點 [Content Invitation Link](https://codeforces.com/contestInvitation/fa8b37a80b9f6ca7701d91ad6e20295bc131599e)
:::

## pA - Edit Distance
顯然只有在 $s_1$ 長度變動時才需要花費費用，且 $|s_1|$ 增加 $1$ 或減少 $1$ 花費都是 $1$。因此答案就是兩字串的長度差，即 $||s_1|-|s_2||$。

## pB - GCD

:::spoiler Observation 1
**Observation 1:** 不論進行了詢問 $1$ 多少次，任意相鄰兩項的最大公因數必為 $1$。
**Proof:** 考慮任意相鄰三項 $a_{i-1},a_i,a_{i+1}$。在對位置 $i$ 進行一次操作以後，這三項變成 $a_{i-1},a_i+a_{i-1}a_{i+1},a_{i+1}$。
由最大公因數的性質 $\forall x,y \in \mathbb{N}, \gcd(x,y)=\gcd(x \bmod y,y)$ 可以知道

$\gcd(a_i+a_{i-1}a_{i+1},a_{i-1})=\gcd((a_i+a_{i-1}a_{i+1})\bmod a_{i-1}, a_{i-1}) = \gcd(a_i \bmod a_{i-1}, a_{i-1}) = \gcd(a_i,a_{i-1})$

用類似方式也可以證明 $\gcd(a_i+a_{i-1}a_{i+1},a_{i+1})=\gcd(a_i,a_{i+1})$。
因此相鄰兩項的最大公因數恆不變。而一開始時，對於所有介於 $1$ 到 $n-1$ 的整數 $i$ 都有 $\gcd(a_i,a_{i+1})=\gcd(i,i+1)=1$，因此任意相鄰兩項之最大公因數恆為 $1$。
:::

由以上觀察，得知最終作法如下：
* $type=1$ 時直接依照題目指示操作即可。
* $type=2$ 時，若 $l=r$ 則直接輸出 $a_l \bmod M$ 的值，否則輸出 $1 \bmod M$。

## pC - Shortest Paths
首先容易發現如果整數 $u,v$ 滿足 $1 \leq u < v \leq n$，且 $(u,v)$ **不是**被拔掉的邊之一，則 $u$ 到 $v$ 的最短路徑就是 $1$。

否則考慮任意一條被拔掉的邊 $(u,v)$。定義 $dist_{x,y}$ 為結點 $x$ 到結點 $y$ 的最短路徑長，無法抵達時定義為 $\infty$。則可以發現

$dist_{u,v} = \min\limits_{u<w<v, w \in \mathbb{N}} dist_{u,w}+dist_{w,v}$

最短路徑長便能在 $O(n)$ 時間內算出來。

因此最終演算法如下：

* 對於所有滿足 $1\leq u < v \leq n$ 的整數 $u,v$ 計算出 $dist_{u,v}$ 的值。
* 依照 $v-u$ 由小到大的順序計算 $dist_{u,v}$ 的值。如果 $(u,v)$ 不是被拔掉的邊則 $dist_{u,v}=1$，否則 $dist_{u,v} = \min\limits_{u<w<v, w \in \mathbb{N}} dist_{u,w}+dist_{w,v}$。
* 每筆詢問就能在 $O(1)$ 求出來。

整體時間複雜度為 $O(n^2 + nm + q)$。

## pD - Colorful Wall
首先先有以下兩個 Observation：
:::spoiler Observation 1
**Observation 1:** 如果存在解，則必定有一個解，使得每行或每列被塗**最多**一次。
**Proof:** 令 $op$ 是任意一個滿足題意的操作序列。假設 $op_i$ 與 $op_j$ 都是對同一行或同一列染色且 $i<j$，則 $op$ 移除 $op_i$ 以後依然是一個滿足題意的解。
:::

:::spoiler Observation 2
**Observation 1:** 如果存在解，則必定有一個解，使得每行或每列被塗**恰好**一次。
**Proof:** 接續 Observation 1 的證明，令 $op$ 是任意一個滿足題意的操作序列，且每一行或每一列最多被塗一次。假設 $nop$ 是 $op$ 中**沒有**出現的行或列的操作序列（排列順序任意），則把 $nop$ 放在 $op$ 的前面依然是一個滿足題意的解。
:::

由以上兩個觀察可以知道必定有一個解是每行或每列都恰好塗一次，也就是恰好 $n+m$ 次操作。

再來看每一格的染色情形。每一格 $(r,c)$ 都恰好被塗兩次，一次是第 $r$ 列的染色 $a_r$，另一次是第 $c$ 行的染色 $b_c$。

依照這格與對應行與列的顏色可以有以下推論：
* 若 $color_{r,c} \neq a_r$ 且 $color_{r,c} \neq b_c$，則無解。
* 若 $color_{r,c} = a_r$ 且 $color_{r,c} \neq b_c$，則第 $c$ 行必定比第 $r$ 列**先**染色。
* 若 $color_{r,c} \neq a_r$ 且 $color_{r,c} = b_c$，則第 $r$ 列必定比第 $c$ 行**先**染色。
* 若 $color_{r,c} = a_r$ 且 $color_{r,c} = b_c$，則哪一個先塗都沒差。

因此有最多 $nm$ 個「第 $r$ 列比第 $c$ 行先/後塗的條件」，可以使用拓樸排序決定是否有解與找出一個染色順序。複雜度為 $O(nm)$。

## pE1 - Red and Blue (Easy Version)
答案是 $\frac{r-b}{r+b}$。

這題有一個兩個版本都適用的解法（在 E2 題解裡面），但是這個版本可以使用以下遞迴 DP 式打表後找規律：

$dp_{r,b}=\begin{cases}
1 & \quad \text{if } b=0\\
0 & \quad \text{if } r=b \\
\frac{r}{r+b} dp_{r-1,b} + \frac{b}{r+b} dp_{r,b-1} & \quad\text{otherwise} \\
\end{cases}$

## pE2 - Red and Blue (Hard Version)
首先先把問題轉換成以下形式：

* 你要寫一個含有恰好 $r$ 個 `R` 和 $b$ 個 `B` 的字串。每一次選擇字元時，如果剩下要寫 $r'$ 個 `R` 和 $b'$ 個 `B`，則選到 `R` 的機率是 $\frac{r'}{r'+b'}$，選到 `B` 的機率是 $\frac{b'}{r'+b'}$。
* 定義一個字串是好的，代表每個後綴中，`R` 出現次數 $r'$ 和 `B` 出現次數 $b'$ 滿足 $r'-b' \leq k$，或者 $b'=0$。
* 求產生好的字串的機率。

容易發現兩個問題答案應該要一樣。

再來可以觀察到以下 Observation：

:::spoiler Observation 1
**Observation 1:** 所有 $r$ 個 `R` 和 $b$ 個 `B` 可以產生的 $\binom{r+b}{b}$ 個字串的產生機率都相同。
**Proof:** 可以發現每個字串產生的機率為每個字元機率值個別相乘。分母 $1$ 到 $r+b$ 恰好都出現一次，分子 $1$ 到 $r$ 都出現一次，$1$ 到 $b$ 又另外再出現一次。因此機率為 $\frac{r!b!}{(r+b)!}$，就是 $\frac{1}{\binom{r+b}{r}}$ 。
:::

因此問題變成計算好的字串的數量。

考慮以下問題：你要從 $(0,0)$ 走到 $(r,b)$，每一步只能從現在的點 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$，且每一步都滿足 $y=0$ 或 $x-y \leq r$。

可以發現前 $k+1$ 步都只能往右走，之後就變成從 $(k+1,0)$ 走到 $(r,b)$ 的方法數。根據一路領先（？）問題的解法，答案是 $\binom{r+b-(k+1)}{b} - \binom{r+b-(k+1)}{b-1}$。

故最後答案是 $\frac{\binom{r+b-(k+1)}{b} - \binom{r+b-(k+1)}{b-1}}{\binom{r+b}{r}}$。

## pF - Identity Permutation Decomposition
首先先有以下 Observation：
:::spoiler Observation 1
**Observation 1:** 一個正整數序列 $a$ 擁有 Identity Permutation Deomposition 的充要條件是對於所有正整數 $x$ 與 $a$ 的每個前綴而言，$x+1$ 的出現次數都不超過 $x$ 的出現次數。
**Proof:** 先證明充分性。若 $a$ 擁有 Identity Permutation Deomposition，則 $a$ 的每個前綴都擁有 Identity Permutation Deomposition（把 $a$ 的 decomposition 中隸屬於前綴的項拿出來即可）。因為對於所有正整數 $x$ 而言，每個 Identity Permutation $x$ 的出現次數都不超過 $x+1$ 的出現次數，因此整個前綴 $x$ 的出現次數都不超過 $x+1$ 的出現次數。

再來證明必要性。考慮以下構造 Identity Permutation Deomposition 的演算法：

* 由左至右掃過 $a$，同時維護一個 Identity Permutation 的 multiset $S$。若 $a_i=1$ 則把 $a_i$ 單獨變成一個 Identity Permutation 放進 $S$，否則取出 $S$ 中任意一個長度是 $a_i-1$ 的 Identity Permutation，把 $a_i$ append 到這個排列後面放回 $S$。

可以發現這個演算法不會失敗。因為這個演算法會失敗的時機為 $S$ 中沒有長度為 $a_i-1$ 的 Identity Permutation，但是這時候代表 multiset 中 $a_{i-1}$ 與 $a_i$ 出現次數相同，加上 $a_i$ 以後代表 $1$ 至 $i$ 這個前綴 $a_i$ 的出現次數超過 $a_{i-1}$，不符合預設條件。
:::

因此我們需要知道每次修改完後，對於所有介於 $1$ 到 $n-1$ 正整數 $x$ 與 $a$ 的每個前綴而言，$x+1$ 的出現次數是否都不超過 $x$ 的出現次數。有以下兩種作法

1. （非預期解）直接開 $n-1$ 棵動態開點線段樹維護。每棵線段樹需要支援區間加值與求整棵樹最小值，第 $i$ 棵線段樹維護前綴 $i$ 出現次數扣 $i-1$ 出現次數的最小值。每次修改相當於 $4$ 次線段樹操作。如果小心實作可能不會 MLE。
2. 稍微修改上面的做法，這次把所有操作都用一棵線段樹完成（同時改為離線）。以上做法中每棵線段樹會在什麼時候被改到是確定的，可以把對該棵線段樹的修改包成一個 tuple $(time_i, pos_i, val_i)$（第幾筆詢問被改、在第幾個位置要 +1/-1），如果前 $i$ 次操作後存在一個前綴小於 $0$，則代表第 $time_i$ 到 $time_{i+1}$ 之間答案是 No。用類似線段覆蓋的做法就可以知道每筆詢問的答案了。

兩者複雜度都是 $O((n+q) \log n)$。

## pG - Tourism
建一張無向圖 $G$，每個公車站為一個結點，把同一條街上相鄰兩車站建一條邊。則可以發現除了觀光景點的要求外，題目便是要求找出很多鍊與很多環，且對於所有度數為 $2$ 的點，選到的邊不能在同一條街上。

如果從選邊的觀點的話，事實上只要滿足以下條件，選出來的邊就會自動形成許多環與鍊：

* 對於每個公車站而言，其上下相鄰的邊最多只能選一條。
* 對於每個公車站而言，其左右相鄰的邊最多只能選一條。

這是因為，如果選出的邊集合滿足以上條件，則每個點的度數都最多是 $2$，因此一個大小為 $n$ 的連通塊度數和最多只能是 $2n$，代表最多只能有 $n$ 條邊。
如果恰有 $n-1$ 條邊，則連通塊是一棵樹，在每個點度數不超過 $2$ 的情況下只能是一條鍊。
如果恰有 $n$ 條邊，則圖恰含有一個環，在每個點度數不超過 $2$ 的情況下只能是一個穿過所有點的大環。

至於觀光景點的部分，可以發現每個觀光景點最多只會被 $G$ 中的兩條邊穿過，而兩條邊至少要有一條邊被選到。

於是現在問題變成，有一個邊集合可供挑選，請挑選一個集合滿足一些「兩條邊中至多只能挑一條」和「兩條邊中最少要挑一條」的條件，可以利用 2-SAT 解決。