Graph Dijkstra template <typename T> struct Dijkstra { vector<T> dis; vector<int> par; Dijkstra(int n, T inf) { dis = vector<T>(n, inf); par = vector<int>(n, -1); }

給定 $ax \equiv b \pmod m$ 的 $a, b, m$，求解 $x$。 如果 $b$ 不是 $g = gcd(a, m)$ 的倍數，則無解。 我們證他的反向，即有解時，$b$ 一定是 $g$ 的倍數。 有解代表存在 $x_0$ 使得 $a x_0 \equiv b \pmod m$，即存在整數 $y$ 滿足 $a x_0 + my = b$。 因為 $a$ 與 $m$ 都是 $g$ 的倍數，所以 $b$ 一定是 $g$ 的倍數。 如果 $b$ 是 $g = gcd(a, m)$ 的倍數，則解為 $x \equiv \left(\frac{a}{g}\right)^{-1} \frac{b}{g} \pmod{\frac{m}{g}}$

UI Window: Zoom Level Breadcrumbs: Enabled Render line highlight Title bar Font Font Family: Fira Code Font Ligature: true Line Height: 1.35

心得 比賽中解五題，都一次 AC，開心（直到看到 vtuber 最後五分鐘竟然過 F），積分 +71。 另外雖然我聽不懂日語也看不懂日文，但仍想推廣一下這個 vtuber RinSakamichi。她三年前就出道，二年前開始打 atcoder，從以前只能解出三題到這次解出六題，一直在進步，但 youtube 上一直沒什麼觀眾，訂閱數也才 1.1K。若有人感興趣可以去追蹤一下。也許是出於興趣，她三年都沒什麼起色還一直做下去，讓人覺得了不起。 A, B (〃∀〃) C. Doukasen 比賽時沒想到總花費時間除 2 就是相遇的時間，二分搜直接開幹。

Who am I? 一個斷斷續續在玩競程的人，這麼多年過去了依然很菜。最近從 codeforces 轉移至 atcoder，畢竟 atcoder 的比賽時間對台灣友善許多。 喜歡使用 python，但 submit 基本上都用 pypy 而非 cpython，因為在一般運算中 pypy 還是比 cpython 快多了。有時為了使用 AtCoder Library 或確保不 TLE 會改用 c++。 AtCoder (id: amoshuangyc) AtCoder Beginner Contest 223 AtCoder Beginner Contest 222 AtCoder Beginner Contest 184

心得 後半 13 題，比前半 13 題難上不少，讓我慢慢寫。 N. Slimes 給定長度為 $N$ 的序列 $A$，不斷重覆：「合併 $A$ 中的相鄰兩項 $x, y$ 為 $x + y$，花費成本 $x + y$」，直到 $A$ 只剩一個元素。請問在所有合併方法中，總成本最小能是多少？ 設 $f(i, j)$ 為合併 $A$ 的半開區間 $[i, j)$ 為一個元素所需的最小成本。 如同 CLRS 中矩陣乘法的最小成本，我們採用 Divide & Conquer 的技巧。

心得 練習 A, B, C ʕ•͡ᴥ•ʔ D. Even Relation 從節點 0 開始 DFS，遇到長度為奇數的邊，就變色；偶數的邊，顏色不變。 N = int(input())

心得 久違地打了一場…只解出四題，慘。 A, B, C (⋋▂⋌) D. Between Two Arrays 設 $dp[i, j]$ = 合法的 $C_0, C_1, \cdots, C_i$ 數量，且 $C_i = j$。因為 $C_{i - 1}$ 需要少於 $j$ 就可以，可以寫出轉移： $$

心得 無事就來寫 atcoder。 A, B, C, D (⁎˃ᆺ˂) E. Sum Equals Xor $a + b = a \text{ XOR } b$ 意謂著 $a$ 與 $b$ 不能有共同的都是 $1$ 的 digit。這常常出現，要背起來！不能都是 1，也就是不會有進位。然後這題就可以用 Digit Dp 解了。 $$

題目連結 心得 第三題卡了我好久好久，最後跑去先解第四題，10 分鐘 AC，才又回來想第三題。高中就知道我排列組合不好，現在還是不會，我真是太失敗了 ੨( ･᷄ ︵･᷅ )ｼ，我到底該正著算呢？還是反著算呢？這樣算到底會不會重覆算呢？是不是要枚舉 0 的數量，用重複組合？第五題沒解出來，聽說是經典題，讓我好好研究研究。 A, B ʘ‿ʘ C. Ubiquity 一開始的想法是正著算：在 N 個位置中任取兩個位置，放 0 與 9，其他位置數字任填，所以方法數是 ${N \choose 2} \cdot 2! \cdot 10^{N-2}$，然後範測一直過不了，換了各種方式都還是不行。

最近遇到不少 digit dp 的題目，而網上的題解通常是 top-down + 遞歸的方法，但有一些題目，例如 Valid payments，如果硬要用遞歸來解，我覺得解法很不直覺。因此在這篇文章我希望整理並統一我 digit dp 的寫法：bottom up + 遞推。 Valid payments 題目相當於在問：「所有 $A$ 進制的 $N$ 位數中（允許 leading 0）有幾個數 $r$ 滿足 $r$ 與 $X + r$ 沒有共同不為 $0$ 的 digit」，即 $\forall_{0 \le i \lt N}, r_i = 0 \lor (X + r)_i = 0$。 設 $y = X + r$，$c$ 是 carry，直式加法如下： $$ \begin{array}{r} &c_3 &c_2 &c_1 &0 \

心得 賽後寫的。 A. Hands 第一直覺就 Dijsktra 模板用起來，不過既然是賽後才寫還是慢慢想吧，第一題不太可能是模板題。 可以發現對 b 來說，向下一層樓有兩種路線： 直接往下，成本 y。 透過水平的通道到 A 樓，再走斜著的通道回 B，成本 2x。

心得 排 1057，積分 +46。 前二題很快的解出，第三題想不出來，先跳去解第四、第五題。第四題輕鬆過了，第五題在兩個測資會 TLE，回去解第三題，終於在測資的幫忙下弄出來了，最後一點時間將第五題的程式優化，在第 99 分鐘 AC，雖然是假解 XD。第六題也是能解的題目，第三、第五題卡太久了。 拼到最後真的累。  source: 點兔第三季

題目連結 心得 practice。 最近似乎遞推的寫法比較主流，所以我也嘗試用遞推來寫，而非我習慣的遞歸。 A. Frog 1 簡單 dp。 N = int(input())

心得 第四題又卡住，還好最後一分鐘 AC，應該先去解第五題，簡單多了 (︶︹︺) 把上一場加的積分全還回去了 QQ A, B 簽到。 C. To 3 基於 3 倍數的特性，可以得出不可能刪 3 個 digits 或更多。刪 1 個 digit 的情況為有某個 digit 與 「N 對 3 的餘數（r）」相同。刪 2 個的情況是選兩個 digits 出來，他們的和可以組出 r。實作時小心別讓所有的 digits 都被刪掉了。

心得 解出 5 題，積分 +54。 第四題漏看了一個條件，害我花了好久。 第六題竟然直接裸著來，我以為這方法會 MLE 就沒寫，可惜。 source A. ReLU 38 秒，下次挑戰不先測直接 submit XD。

題目連結 心得 第二題鬼打牆，最終解出前三題，排 1245，積分 +35 A. Simple Math A, B, C = map(int, input().split()) A = (1 + A) * A // 2 % 998244353 B = (1 + B) * B // 2 % 998244353 C = (1 + C) * C // 2 % 998244353

題目連結 心得 解五題，排 1387 A, B 略 C. Repsept 序列的數字可能非常大，該怎麼高速地判定某大數是不是 K 的倍數呢？Horner's Rule！這個技巧真常出現。

題目連結 心得 賽後才來寫的，這場比賽跟 cf 連在一起，所以就沒打這場了。 A, B, C 都是水題。 聽說第二題會卡 double，得用 long double 才會過，用 python 的表示有這回事嗎 ¯(°_o)/¯ D. Takahashi Unevolved

題目連結 心得 因為沒同學／朋友要一起參戰，比賽時只來看了一圈題目沒 submit。 A, B, C 水題。 D. Hachi 看完題目想說這麼簡單，怎麼 Standings 上一堆人都先 WA 才 AC，看我一次 AC，然後我就 WA 了三次 (┛ಸ_ಸ)┛彡┻━┻