# AtCoder Beginner Contest 414
Unofficial Editorial
~~為了減少製作成本~~，以下不會幫你翻譯題目，也不會有實作的 code (因為我覺得要自己想過然後用自己的方式實做出來比較好，不要直接抄)。
如果想看 code ，可以去 submission 找，應該有更多實作比我好看的。
然後這次好多數學喔 QAQ

### A
(●'◡'●)
### B
看懂題目意思然後直接實作即可 ( •̀ ω •́ )✧
### C
:::spoiler ~~觀察 1~~ 數學 1
直接算出小於 $10^{12}$ 的所有回文數字會怎樣 ?
不會怎樣。
長度是 1 的回文數字有 $9$ 個
長度是 2 的回文數字有 $9$ 個
長度是 3 的回文數字有 $9^2$ 個
長度是 4 的回文數字有 $9^2$ 個
長度是 5 的回文數字有 $9^3$ 個
...
長度是 11 的回文數字有 $9^6$ 個
長度是 12 的回文數字有 $9^6$ 個
計算機告訴你加起來總共不超過 $9^6 \times 12 = 6377292$ 個 (非常粗糙的估算)
:::
:::spoiler 實作
寫一個 DFS 之類的東西算出所有小於 $10^{12}$ 的 10 進位的回文數字，再視情況看要不要 `sort` (DFS 寫好的話應該是不用)，再對於每個小於等於 $N$ 的回文數字檢查它在 $A$ 進位下是不是也是回文，是的話就加到答案裡
:::
### D
:::spoiler 觀察 1
收同一個基地台訊號的房子們會分布在一段連續的區間
所以要 ||sort||
:::
:::spoiler 觀察 2
蓋 $k$ 個基地台 = 把房子們分成 $k$ 組 (可以參考下圖)
:::
:::spoiler 觀察 3
所以要選 $k-1$ 個分隔把房子們分開，為了減少蓋基地台的成本，分隔要選 ||越遠越好||
參考下圖 :
:::
:::spoiler 實作
把每個分隔距離拿去 `sort`，然後選最大的 $k-1$ 個，觀察一下發現 ||用總距離把它們減掉|| 就是答案
:::
:::spoiler 複雜度
$O(nlogn)$
因為排序
:::
### E
:::spoiler ~~觀察 1~~ 數學 1
如果在 $[2, N]$ (因為你會發現 $a$ 、 $b$ 都不可以放 $1$) 中隨便挑兩個不一定不同的 $a$ 和 $b$ 滿足 $a \bmod b = c$，觀察不滿足題目要求的情況：
1. $a=b$ : 你挑的 $a$ 和 $b$ 剛好一樣，~~這是廢話~~
2. $b=c$ : 不可能
3. $a=c$ : $b>a$
4. $c=0$ : 你挑的 $a \bmod b=0$

所以如果你挑的 $a$ 大於你挑的 $b$，123 就不會發生，這樣的挑法共有 $\frac{(n - 1)(n - 2)}{2}$ 種
:::
:::spoiler ~~觀察 2~~ 數學 2
剩下第 4 種情況要扣掉，對於每個 $b$，一共有 $\left\lfloor \frac{n}{b} \right\rfloor - 1$ 個 $a$ 滿足第 4 種情況，然後可以寫出以下的 code :

cin >> n;
ll all=((n-1)%mod*((n-2)%mod)%mod)*inv%mod;

for( int i=2 ; i<n ; i++ ){
    all=(all-n/i+1+mod)%mod;
}
cout << all;

(`inv` 是 2 的模逆元)
然後這個 code 是 $O(n)$，會 TLE
:::
:::spoiler ~~觀察 3~~ 數學 3
優化！！！
發現這題和 CSES [Sum of Divisors](https://cses.fi/problemset/task/1082/) 一樣，不要枚舉 $b$，改成枚舉 $\left\lfloor\frac{n}{b} \right\rfloor$
因為 $\left\lfloor\frac{n}{b} \right\rfloor$ 最多有 $2\sqrt{n}$ 個，可以 $O(\sqrt{n})$ 算完
:::spoiler 為什麼
因為我不會嚴謹的數學證明，所以以下只會有直觀的觀察和不嚴謹的解釋
令 $n=12$，觀察下表
| $b$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| $\left\lfloor\frac{n}{b} \right\rfloor$ | 6 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |

你會發現 $\left\lfloor\frac{n}{b} \right\rfloor$ 是 $n$ 的因數們，而 $n$ 的因數不超過 $2\sqrt{n}$ 個
注意 : 這只是某個看起來比較直觀的特例，像是取 $n=13$ 就不會滿足上述的話，~~但你會發現不會差太多~~
:::
[數學證明](https://math.stackexchange.com/questions/1069460/how-many-distinct-values-of-floorn-i-exists-for-i-1-to-n)
:::spoiler 複雜度
$O(\sqrt{n})$
:::
### F
:::spoiler 觀察 1
很像 BFS，但它一次跳 $k$ 步
可以用 `vis[邊][r]` 表示是否曾經在 $d \bmod k=r$ 經過這條邊 ($d$ 是走的距離)
:::
:::spoiler 觀察 2
如果想用 BFS 算答案，先開一個 `queue` 存 `{目前在點 i, 目前走了 d 步, 剛剛是從邊 e 走到 i 的}`
如果 $d \bmod k=0$ 而且點 $i$ 的答案目前是未知的，就更新點 $i$ 的答案
然後嘗試所有 $i$ 連接的點，假設目前嘗試往 $u$ 走，則
1. `vis[i->u][(d+1)%k]=true` 代表走過了，不用再試了
2. $i$ 走到 $u$ 的那條邊就是 $e$
1. $d \bmod k=0$ 那就走回去試試看
2. $d \bmod k \neq 0$ 那就不能走，不然會一直在這兩個點之間折返跑

這樣複雜度最壞有 $O(N^2K)$
:::spoiler 為什麼
考慮星狀圖，長這樣
每種 `vis` 的狀態會被放進 `queue` 一次 ($O(NK)$)，遍歷所有鄰邊又會再跑 $O(N)$ 次
:::
:::spoiler 觀察 3
假設我們目前走了 $d_1 \bmod k=r$ ($r \neq 0$) 步到達點 $v$，且點 $v$ 是從點 $a$ 來的，他下一步可以走到 $b$、$c$、$d$ :

假設之後又從點 $b$ 共走了 $d_2 \bmod k=r$ ($r \neq 0$) 步到達點 $v$，他下一步只可以走到 $a$，因為 $c$ 和 $d$ 相同的狀態已經走過了 :

假設之後又從點 $c$ 共走了 $d_3 \bmod k=r$ ($r \neq 0$) 步到達點 $v$，他下一步沒地方可以走了，因為 $a$、$b$ 和 $d$ 相同的狀態已經走過了 :

所以可以放一個 `cnt[i][r]`，表示在 $d \bmod k=r$ 拜訪點 $i$ 幾次 ($d$ 是走的距離)，且最多只要拜訪 ||兩次||，這樣就有 $O(NK)$ 了 ヾ(≧▽≦*)
:::
:::spoiler 複雜度
$O(NK)$
:::