第二類斯特林數(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) $$ 而第二類斯特林數有以下性質： ...
又稱模倒數、模逆元，簡稱$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$ ...