一些数学知识

· · 算法·理论

首先这个东西只给自己用

C(n, m) = C(n - 1, m - 1) + C(n - 1, m) n个数字选m个数

第二类斯特林数表示将n个元素划分到m个不同的集合中的方案数

S(n, m) = S(n - 1, m - 1) + S(n - 1, m) * m

第n个，要么独立新建一个，要么到之前的去

逆元

费马小定理求逆元

a^{p - 1} \equiv a * a^{p - 2} \equiv 1 \bmod p

条件：a \perp p

线性求逆元

ik + a \equiv 0 \bmod p \\ ik \cdot i^{-1}a^{-1} + a \cdot i ^{-1}a ^{-1} \equiv 0 \bmod p \\ ka ^ {-1} + i ^ {-1} \equiv 0 \bmod p \\ i ^ {-1} \equiv -k a^{-1} \bmod p\\ i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \cdot inv_{p \bmod i} \bmod p\\

条件：p为素数，否则可能存在不存在的逆元

inv[i] = (p - p \ i) * inv[p % i] % p;