跳转至

一些黑科寄

数论

线性逆元

给定 \(n\) 个数，第 \(i\) 个数为 \(a_i\)，要求在 \(O(n)\) 的时间内求出每个数的逆元。

设 \(b_i = \prod_{j=1}^i a_i, c_i = (b_i)^{-1}\)，则：

\[ \begin{aligned} b_i &= a_i b_{i-1} \\ c_i &= a_{i+1} c_{i+1} \\ (a_i)^{-1} &= b_{i-1} c_i \end{aligned} \]

代码

1
2
3
4
5
6
prod[0] = 1;
for (int i = 1; i <= n; ++i)
    prod[i] = mul(prod[i - 1], num[i]);
inv[n] = power(prod[n], MOD - 2);
for (int i = n; i; --i)
    inv[i - 1] = mul(inv[i], num[i]), inv[i] = mul(inv[i], prod[i - 1]);

快速乘

两个 long long 范围内的数乘起来对 long long 范围内的数取模。

解释见 OI WiKi。

代码

1
2
3
4
5
6
7
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
ll mul(ll a, ll b, ll mod) {
    ull c = (ld)a / mod * b + 0.5L, ans = (ull)a * b - c * mod;
    return ans < mod ? ans : ans + mod;
}