什麼是檔案？ 在 Unix 系統中，有「everything is a file」的概念，如硬體設備、進程資訊、網路連線、處理器狀態等都抽象化為檔案系統中的一個路徑。透過這種設計，使用者只需要使用一套統一的 API（例如 open(), read(), write(), close()），就能操作各種截然不同的系統資源，而不需要為每一種硬體另外撰寫專屬的操作介面。比方說 /proc/cpuinfo 這個路徑包含了 CPU 資訊， /dev/sda 則代表整顆實體硬碟。 ...
什麼是 Kernel？ 一般指稱的 Linux 其實不是作業系統，而是 Kernel 的一種。 Kernel（內核），是處在硬體與軟體之間的程式，它主要負責分配硬體資源給軟體、控制硬體功能，同時把與硬體溝通的複雜流程簡化；相比之下，作業系統（Operating System），則是包含 Kernel 在內的大程式，加入許多面向一般使用者的應用程式、GUI 等等更多方便的功能。 ...
Bellman-Ford Bellman-Ford 可以在有負邊的圖 （不論有向無向）上找出單源最短路，還可以偵測負環。在最短路存在的情況下，由於每次鬆弛最少會使最短路的邊數$+1$，而最短路的邊數最多為 $n - 1$ （每個節點最多經過一次），因此最多進行 $n - 1$ 次鬆弛操作。若到了第 $n$ 次迴圈還可以繼續鬆弛，則代表該圖存在負環。 ...
原理 令當前要處理的數為 $i$，已找到的質數列表為 primes： 遍歷 $i$ 從 $2$ 到 $N$。 若 $i$ 未被標記為合數，則 $i$ 為質數，加入 primes。 用 $i$ 與 primes 中的質數 $p$ 相乘（標記合數 $x = i \times p$）： 標記 $i \times p$ 為合數。 關鍵關鍵條件：若 $i \pmod p == 0$，立即中斷（break）內部迴圈。 為什麼 i % p == 0 時要 break？ 線性篩規定「每個合數只能由它的最小質因數篩掉」，若 $p$ 能整除 $i$，表示 $p$ 是 $i$ 的最小質因數。 如果繼續使用下一個更大的質數 $p_{next}$ 來標記 $i \times p_{next}$，該數的最小質因數其實是 $p$ 而非 $p_{next}$。這樣會導致 $i \times p_{next}$ 未來又被別的更大的 $i$ 和 $p$ 重複篩到，破壞線性時間。 ...
線段樹是一種資料結構，也可以說是一種分冶想法，用來在 $O(\log N)$ 內處理區間查詢、區間修改的問題。 甚麼是區間問題 比較簡單的區間問題如下： 有一個序列 $a_1, a_2, a_3, \cdots, a_n$ ，且有 $q$ 筆操作，操作有兩種： ...
甚麼是最大流問題 想像有一張由水管連接而成的網路，每條水管有容量限制，流過的水流不能超過這條水管的容量。這張圖上有兩個特別的節點：源點和匯點，源點是無限供水的地方，而匯點是收集水的地方。 source: https://www.geeksforgeeks.org/dsa/ford-fulkerson-algorithm-for-maximum-flow-problem/ 目標：調整各條管線的流量，讓匯點 $T$ 能有最大輸入。 名詞介紹 網路 Network：一個有向圖 源點與匯點 Source and Sink：源點 $S$ 為網路流的起點、匯點 $T$ 為網路流的終點，其餘點為中間點 流量 Flow：每條邊上的數值，表示經過該條邊的流量，計為 $f(u,v)$ 容量 Capacity ：每條邊上的最大流量，計為 $c(u,v)$ 殘餘容量 Residual Capacity：每條邊上容量減去流量的值，計為 $r(u,v) = c(u,v) - f(u,v)$ 剩餘網路 Residual Network：計算每條邊上的殘餘容量，以 $r(u,v)$ 畫成新的一張圖 網路流量：由源點出發至匯點的總流量，若該值達到最大，則稱為「最大流」 增廣路徑：在殘餘網路中，存在一條從源點 $S$ 到匯點 $T$ 的路徑，其路徑上的每一條邊殘餘容量皆大於 0（$r(u,v) > 0$），只要能找到增廣路徑，就代表當前的總流量還可以再增加 反向邊：殘餘網路還包含了反向邊，流量為 $f(u, v)$。反向邊的作用是給予演算法反悔的機制，當發現從不同路徑能夠達到的流量更大，且兩個路徑經過同一條邊但相反方向時，反向邊可以抵消原本的流量，讓兩條路徑分開為不同路徑，此時這條邊的實際流量就會是 0。 舉個反向邊的例子，考慮以下流量網路： 如果演算法先找到了 $S \rightarrow A \rightarrow B \rightarrow T$ 這條路徑，輸送了 10 單位的流量，此時 $A \rightarrow B$ 這條邊已經被占滿了。其實最佳解法應該是 $S \rightarrow B$ 與 $A \rightarrow T$ 這兩條路可以組出 $S \rightarrow B \rightarrow T$ 與 $S \rightarrow A \rightarrow T$ 這兩條路徑，可以組出 20 單位的流量，如果第一步時在 $A$ 、 $B$ 之間建立建立一條反向邊 $B \rightarrow A$ ，演算法就可以繼續走 $S \to B \to A \to T$。此時從 $A \to B$ 的流被抵銷了，兩條路徑被拆成都不經過 $A \to B$ 這條邊。 ...
第二類斯特林數(Stirling Number of the 2nd Kind)，是用來計算一種問題： 將 $n$ 顆不同的小球放入 $k$ 個相同的箱子中，不允許空箱，有幾種方法數？ 通常記做 $S(n, k)$ 或 $\begin{Bmatrix}n\\ k\end{Bmatrix}$。 如何計算 可以思考一下，現在有 $n$ 顆球， $k$ 個箱子： $n - 1$ 顆球已經被放到了 $k - 1$個箱子中，現在要放入最後一顆球到最後一個空的箱子。 方法數會是 $S(n - 1, k - 1)$。 $n - 1$ 顆球已經被放到了 $k$ 個箱子中，現在要放入最後一顆球到其中一個箱子。 方法數會是 $C^n_1 \times S(n - 1, k)$ 。 因此可以寫出 $S(n, k)$ 的遞迴式： $$ S(n, k) = S(n - 1, k - 1) + C^n_1 \times S(n - 1, k) $$ 而第二類斯特林數有以下性質： ...
由於 $C^n_r$ 是階乘，直接硬算會算很久，因此預先處理來快速算出組合數尤為重要。 想法是利用模反元素，將除以 $k!$ 改成乘以 $k!$ 的模反元素。這個方法預處理的時間複雜度為 $O(N)$，之後就能用 $O(1)$ 查詢。 步驟： 先開一個陣列紀錄 $0! \sim n! \pmod M$ 的值 計算 $n! \pmod M$ 的模逆元，再開一個陣列紀錄 $k! \sim 0!$ 的模逆元。 只要先求出 $(k!)^{-1}$ ，就可以利用 $(k!)^{-1} = (k + 1)!^{-1} \times (k + 1) \pmod M$ 來由大到小得出所有階乘的模逆元。 查詢時，只要利用 $C^n_k = n! \times (k!)^{-1} \times ((n - k)!)^{-1} \pmod M$ 在 $O(1)$ 得出。 #define MOD 1000000007LL #define MAXN 200005 #define ll long long using namespace std; ll qpow(ll a, ll b) { ll res = 1; a %= MOD; while (b > 0) { if (b & 1) { res = res * a % MOD; } a = a * a % MOD; b >>= 1; } return res; } ll inverse_mod(int a) { return qpow(a, MOD - 2); } ll fact[MAXN], inv_fact[MAXN]; void precompute_combination() { fact[0] = 1; inv_fact[0] = 1; for (int i = 1; i < MAXN; i++) { fact[i] = fact[i - 1] * i % MOD; } inv_fact[MAXN - 1] = inverse_mod(fact[MAXN - 1]); for (int i = MAXN - 2; i >= 1; i--) { inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD; } } ll nCr(int n, int r) { if (r < 0 || r > n) return 0; return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD; }
後綴是甚麼？ 比方說字串 S = banana，S的所有後綴就是： banana anana nana ana na a 將這些後綴排序後： a ana anana banana na nana Suffix Array就是將字串的每個後綴進行排序後，紀錄該後綴開頭index的陣列： int SA[N]; SA[i]; // 表示順序第i個後綴的開頭index 如果 SA[3] = 0 ，表示字典序第 4 小的後綴是從 S[0] 開頭的，也就是 banana。 例題：算出 s = "aba" 的 SA 陣列 ans SA[3] = {2, 0, 1}; 怎麼找出 Suffix Array ？ 暴力法就是把所有後綴抓出來，然後進行排序。顯然這個方法的時間複雜度是 $O(N^2\log N)$ (別忘了比較兩個字串要 $O(N)$)。 ...
又稱模倒數、模逆元，簡稱$MMI$或$inv$ 如果$a$跟$n$互質 那一定有一個$b$，讓$(a \times b) \mod n = 1$ 或$(a \times b - 1)$可以整除$n$ 這時候$b$就是$a \mod n$的模反元素 而且$b + kn, k \in Z$ $b + kn$都是$a \mod n$的模反元素 用途 在求$a \div b \mod p$時，如果$a$、$b$太大無法直接相除 需要把$\div b$替換成$\times c$，並使$a \div b \equiv a \times c \pmod p$ 這樣就可以拆成$(a \mod p) \times (c \mod p)$ 而這個$c$就是模反元素 處理溢位時尤為好用 舉例 $3$、$11$互質 $inv = 4$ $3 \times 4 \mod 11 = 1$ 所以根據定義： $4 + 11k = 4, 15, 26 ...$ $3 \times 15 \mod 11 = 1$ $3 \times 26 \mod 11 = 1$ $...$ $3 \times (4 + 11k) \mod 11 = 1, k \in Z$ ...