筆記

由於 $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$ ...