8.17 后记

T1

原来组合数有通项公式（大雾）

线性求逆元：

显然，\(1^{-1}\equiv 1(\operatorname{mod} p)\)

令 \(k=\lfloor \frac{p}{i} \rfloor,j=p\operatorname{mod}i\)，则 \(p=i\times k+j\)

则 \(0\equiv i\times k+j (\operatorname{mod} p)\)

两边同时乘 \(i^{-1}\times j^{-1}\)

得 \(0\equiv k\times j^{-1}+i^{-1}(\operatorname{mod} p)\)

移项得 \(i^{-1}\equiv -k\times j^{-1}(\operatorname{mod} p)\)

代入得 \(i^{-1}\equiv \lfloor \frac{p}{i} \rfloor \times j^{-1}\)

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

考虑逆元的意义为模意义下倒数，则 \(fac_i^{-1}\equiv fac_{i+1}^{-1}\times (i+1)(\operatorname{mod} p)\)

T2

扫描线，二位数点

T3

T4