算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演

算法,学习,笔记,狄利克,卷积,莫比,乌斯,反演 · 浏览次数 : 140

小编点评

**二项式反演** 二项式反演是指偏序集上莫比乌斯反演。设 \\(A\\) 和 \\(B\\) 是 \\(X_n\\) 的子集,且 \\(A \\subseteq B\\),有 \\(\\mu(A, B) = (-1)^{|B| - |A|}\\)。这可以通过归纳假设证明,这里不过多展开。 **狄利克雷卷积上的莫比乌斯反演** 其实就是偏序集上莫比乌斯反演。设 \\(A\\) 和 \\(B\\) 是 \\(X_n\\) 的子集,且 \\(A \\subseteq B\\),有 \\(\\mu(A, B) = (-1)^{|B| - |A|}\\)。这可以通过归纳假设证明,这里不过多展开。 **容斥** 容斥是指在偏序集上求解莫比乌斯反演。设 \\(A\\) 和 \\(B\\) 是 \\(X_n\\) 的子集,且 \\(A \\subseteq B\\),有 \\(\\mu(A, B) = (-1)^{|B| - |A|}\\)。这可以通过容斥求解,最终得到 \\(f(x) = \\frac 1n \\sum_{k = 0}^{n - 1} \\omega^{-kx} g(k)\)。

正文

狄利克雷卷积和莫比乌斯反演

看了《组合数学》,再听了学长讲的……感觉三官被颠覆……


狄利克雷卷积

如此定义:

\[(f*g)(n) = \sum_{xy = n} f(x)g(y) \]

或者可以写为

\[(f * g)(n) = \sum_{d | n} f(d) g(\frac nd) \]


特殊的函数

  • 单位根 \(\varepsilon\):满足 \(f * \varepsilon = \varepsilon * f = f\)

\[\varepsilon(n) = \left\{ \begin{gathered} & 1, \text{if n = 1} \\ & 0, \text {otherwise} \end{gathered} \right. \]

  • 幂函数 \(Id_k(n) = n^k\)。特殊的,\(Id_1(n) = n\) 为恒等函数,\(Id_0(n) = 1\) 为常函数,简记为 \(I\)
  • 除数函数 \(\sigma_k(n) = \sum_{d|n}^{} {d^k}\)。特殊的,\(\sigma_1(n)\) 为因数和函数,简记为 \(\sigma(n)\)\(\sigma_0(n)\) 为因数个数函数,简记为 \(\tau(n)\)
  • 欧拉函数 \(\varphi(n)\)。质因数分解 \(n = p_1^{c_1}p_2^{c_2}...p_k^{c_k}\),则 \(\varphi(n) = n \prod_{i = 1}^k \cfrac {p_i - 1}{p_i}\)

这些函数都是积性函数,满足 \(gcd(i, j) = 1 \implies f(ij) = f(i)f(j)\)


函数之间的关系

可能有不完整的地方……

其中可以通过 \(I\) 转化的,都可以通过 \(\mu\) 转换回去。考虑 \(I * \mu = \varepsilon\) 的事实,后面会讲。

除数函数和幂函数

根据定义,我们有

\[(Id_k * I)(n) = \sum_{d|n}^{} {Id_k(d)} = \sum_{d|n}^{} {d^k} = \sigma_k(n) \]

\[Id_k * I = \sigma_k \]

欧拉函数和恒等函数

根据卷积:

\[(\varphi * I)(n) = \sum_{d | n}^{} {\varphi(d)} \]

\(n = p^k\) 时(\(p\) 为质数),有:

\[\sum_{d|n}^{} {\varphi(d)} = \varphi(1) + \sum_{i = 1}^{k} {\varphi(p^i)} = 1 + \sum_{i = 1}^{k} {p^i - p^{i-1}} = p^m = d \]

所以 \((\varphi * I)(p^k) = p^k\)

\(n\) 质因数分解为 \(\prod p^k\),根据积性函数的定义,可知:

\[(\varphi * I)(n) = n = Id_1(n) \]

莫比乌斯函数和欧拉函数

应该把后面看完了再回来看这个……

莫比乌斯函数定义为:

\[\mu * I = \varepsilon \]

根据: \(\varphi * I = Id_1\),两边同时卷上 \(\mu\)

有:

\[\varphi * I * \mu = Id_1 * \mu \iff \varphi = Id_1 * \mu \]


狄利克雷卷积的逆元

对于一个函数 \(f\),我们可以如下的定义一个函数 \(g\)

首先设 \(g(1) = \frac 1 {f(1)}\)

然后令 \(g(x) = - \frac 1 {f(1)} \sum_{d | x, d > 1}^{} {g(d)f(\frac xd)}\)

于是 \((f * g) = \varepsilon\)

展开带入证明即可。


莫比乌斯函数与莫比乌斯反演

终于到这里了 QwQ

我们定义莫比乌斯函数是 \(I\) 的逆函数,也就是说 \((\mu * I) = \varepsilon\)

所以,在狄利克雷卷积中:

\[\mu(n) = \begin{cases} 1 & if\ n = 1 \\ 0 & if\ \exists x \exists k, n = kx^2 \\ (-1)^m & n = p_1p_2...p_m \end{cases} \]

至于为什么强调狄利克雷卷积……后文会提及。

莫比乌斯函数常用于以下形式

\[g(n) = \sum_{d | n}^{} {f(d)} \iff f(n) = \sum_{d|n}^{} {\mu(d)g(\frac nd)} \]

或者可以写作:

\[f * I = g \iff f = g * \mu \]

而这就是莫比乌斯反演的核心公式。

很简单的公式,根本无需记忆……

求法

和欧拉函数 \(\varphi\) 类似,可以通过线性筛的方法在 \(O(n)\) 内求出。

vector<int> prms;
int mob[N], notp[N];
void getMob(int n) {
    mob[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!notp[i])
            mob[i] = -1, prms.push_back(i);

        for (int p : prms) {
            int ip = i * p;
            if (ip > n) break;
            notp[ip] = 1;
            if (i % p == 0) {
                mob[ip] = 0;
                break;
            } else mob[ip] = -mob[i];
        }
    }
}

数论分块(整除分块)

这部分虽然不属于莫比乌斯反演,但是在求很多相关问题的时候需要用到。

开篇膜拜 Pecco 大佬:# 算法学习笔记(36): 莫比乌斯反演

核心问题:求解 \(\sum_{i = 1}^n \lfloor \frac ni \rfloor, n \le 10^{12}\)

不难得知, \(\lfloor \frac ni \rfloor\) 不同的取值只有 \(O(\sqrt n)\) 个,并且是连续的。所以考虑对于每一种取值,求出有其总贡献。问题转化为,对于 \(i\),需要求出满足 \(\lfloor \frac ni \rfloor = \lfloor \frac nj \rfloor\) 的最大的 \(j\)

于是设 \(\lfloor \frac ni \rfloor = k\)

\[\lfloor \frac nj \rfloor = k \implies k \le \frac nj \le k + 1 \\ \implies \frac 1 {k+1} < \frac jn \le \frac 1k \implies j \le \frac nk \implies j \le \lfloor \frac n{\lfloor \frac ni \rfloor} \rfloor \]

也就是说,对于每一个取值 \(\lfloor \frac ni \rfloor\),最大在 \(\lfloor \frac n{\lfloor \frac ni \rfloor} \rfloor\) 时满足。

于是可以这样写出代码:

for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

练习题:[CQOI2007]余数求和 - 洛谷


补充:现在我们考虑更极端的情况,例如求:

\[f(n) = \sum_{i = 1}^n g(\lfloor \frac ni \rfloor) \]

其中:

\[g(n) = \sum_{i = 1}^n \lfloor \frac ni \rfloor \]

写出来 \(n = 1e9\) 的时候可以轻松过掉。其复杂度为 \(O(n^{\frac 34})\),证明见讨论。

膜拜 @jijidawang in 讨论

所以见到类似的数论分块套数论分块,大胆的写下去吧!


其实数论分块不仅仅可以解决 \(\lfloor \frac ni \rfloor\) 的问题,也可以套用在 \(\sqrt i\) 的问题上。写法十分类似。这里就不做过多讲解。


莫比乌斯反演的经典结构

莫比乌斯反演的经典套路其实就是 \(\varepsilon, \varphi, \mu, I, Id\) 的灵活应用和转换,以及交换合式的小技巧。

其中有 \(\varepsilon(x) = [x = 1] = \sum_{d|x} \mu (d), Id(x) = x = \sum_{d | x} \varphi(x)\)

结构1

\[[\gcd(i, j) = 1] = \varepsilon(\gcd(i, j)) = \sum_{d|\gcd(i, j)} \mu (d) \]

于是对于:

\[\begin{aligned} &\sum_{i = 1}^{n}\sum_{j = 1}^m [\gcd(i, j) = 1] \\ = &\sum_{i = 1}^{n}\sum_{j = 1}^m \sum_{d|\gcd(i, j)} \mu (d) \end{aligned} \]

在这里,有一个非常经典的处理方法:提取公因数

也就是枚举 \(gcd(i, j)\)

\[\begin{aligned} = &\sum_{d = 1}^{\min(n, m)} \sum_{i = 1}^{\lfloor \frac ni \rfloor} \sum_{j = 1}^{\lfloor \frac nj \rfloor} \mu(d) \\ = &\sum_{d = 1}^{\min(n, m)} \lfloor \frac nd \rfloor \lfloor \frac md \rfloor \mu (d) \end{aligned} \]

于是最终利用数论分块求即可。复杂度为 \(O(n + \sqrt {\min(n, m)})\)

但是代码需要注意,每一次取小步跳:

r = min(n / (n / l), m / (m / l));

结构2

原题:GCD SUM - 洛谷

\[\gcd(i, j) = Id_1(\gcd(i, j)) = (I * \varphi)(\gcd(i, j)) = \sum_{d | \gcd(i, j)}\varphi(d) \]

于是求 \(\sum_{i = 1}^{n}\sum_{j = 1}^m \gcd(i, j)\) 的方法与结构1类似即可。

结构3

\[\begin{aligned} \tau(x) &= \sum_{k | x} 1 \\ \tau(xy) &= \sum_{i | x} \sum_{j | y} [\gcd(i, j) = 1] \end{aligned} \]

于是求 \(\sum_{x = 1}^n \sum_{y = 1}^m \tau(xy)\) 也就很简单了。

结构4

原题:YY的GCD - 洛谷

\(P\) 表示质数集合,求:

\[\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) \in P] \]

我们首先提取公因数:

\[= \sum_{p \in P} \sum_{i = 1}^{\lfloor \frac np \rfloor} \sum_{j = 1}^{\lfloor \frac mp \rfloor} [gcd(i, j) = 1] \]

于是根据模型1:

\[= \sum_{p \in P} \sum_{x = 1}^{\lfloor \frac {\min(n, m)}{p} \rfloor} \mu(x) \lfloor \frac n{px} \rfloor \lfloor \frac n{px} \rfloor \]

接下来是一个非常经典的套路:枚举 \(T = px\)

\[= \sum_{T = 1}^{\min(n, m)} \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{p | T, p \in P} \mu(\frac Tp) \]

于是问题转化为求 \(\sum_{p | T, p \in P} \mu(\frac Tp)\) 的前缀和,这样就可以单次询问 \(O(\sqrt n)\)

这完全可以通过埃氏筛筛出,复杂度 \(O(n \log \log n)\),十分优秀。

不过也可以通过线性筛筛出(因为这个函数非积性函数,所以这里不展开)。

类似的题还有 [国家集训队]Crash的数字表格 / JZPTAB - 洛谷

问题:\(\sum_{i = 1}^n \sum_{j = 1}^m lcm(i, j)\)

考虑转化为 \(\gcd\),有

\[lcm(i, j) = \cfrac {i j} {\gcd(i, j)} = \gcd(i, j) \times \cfrac i {\gcd(i, j)} \times \cfrac j {\gcd(i, j)} \]

带入原式中,枚举 \(gcd(i, j)\),有:

\[\begin{aligned} &= \sum_{d = 1}^{\min(n, m)} d \sum_{i = 1}^{\frac nd} \sum_{j = 1}^{\frac md} i j [gcd(i, j) = 1] \\ &= \sum_{d = 1}^{\min(n, m)} d \sum_{i = 1}^{\frac nd} \sum_{j = 1}^{\frac md} i j \sum_{t | gcd(i, j)} \mu(t) \\ &= \sum_{d = 1}^{\min(n, m)} d \sum_{t = 1}^{\frac {\min(n, m)}d} \mu (t) t^2 \sum_{i = 1}^{\frac n{dt}} i \sum_{j = 1}^{\frac m{dt}} j \\ \end{aligned} \]

后面部分可以通过 \(g(n) = \frac {n (n + 1)}2\) 简化。

\[= \sum_{d = 1}^{\min(n, m)} d \sum_{t = 1}^{\frac {\min(n, m)}d} \mu (t) t^2 g(\lfloor \frac n{dt} \rfloor) g(\lfloor \frac m{dt} \rfloor) \]

于是只需要预处理 \(\mu(t)t^2\) 的前缀和即可。

但是显然数论分块套数论分块不够优秀,考虑继续优化。

所以枚举 \(T = dt\)

\[= \sum_{T = 1}^{\min(n, m) } g(\lfloor \frac nT \rfloor) g(\lfloor \frac mT \rfloor) T \sum_{t | T} \mu(t)t \]

也就是说只需要线性求出 \(\sum_{t | T} \mu(t)t\) 即可(其满足积性)。

[SDOI2014]数表 - 洛谷

问题:\(\sum_{i = 1}^n \sum_{j = 1}^m \sigma(gcd(i, j))\)

不过这道题要难一些,因为涉及到了更多的操作。

主要就是将询问离线,按照限制的大小一一处理即可。

毒瘤之神的考验 - 洛谷

\(\sum_{i = 1}^n \sum_{j = 1}^m \varphi(ij)\)

需要知道转化式子:

\[\varphi(ij) = \cfrac {\varphi(i) \varphi(j) \gcd(i, j)} {\varphi(\gcd(i, j))} \]

\(\varphi\) 展开即可证明。

于是可以得到玄妙的式子。

然后通过值域分治求解即可。

……说着简单

化简后有三个函数:

\[\begin{aligned} f(n) &= \sum_{d | n} \cfrac {d \mu (\frac n d)}{ \varphi(d) } \\ g(n, t) &= \sum_{i = 1}^n \varphi(i t) \\ h(n, m, t) &= f(t) * g(n, t) * g(m, t) \\ \end{aligned} \]

原式为:

\[\sum_{t = 1}^{\min(n, m)} h(\lfloor \frac nt \rfloor, \lfloor \frac mt \rfloor, t) \]

显然,由于 \(h\) 的状态数很恨很多,所以考虑值域分治。

\(\frac nt\) 比较大的时候暴力求解,到很小的时候再利用预处理的前缀和快速求解。

类似于 \(\sqrt n\) 分治吧。

于是你可以写出类下的代码:

lint solve(lint n, lint m) {
    if (n > m) swap(n, m);

    lint ans = 0;
    for (lint i = 1; i <= min(n, S); ++i)
        (ans += h(i, n / i, m / i)) %= mod;

    for (lint l = S + 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += t[n / l][m / l][r] - t[n / l][m / l][l - 1] + mod;
        ans %= mod;
    }

    return ans;
}

其中 \(S\) 表示分治的边界,\(t\) 表示对于 \(h\) 在第三个参数位置的前缀和。

预处理也是很简单:

inline lint h(int t, int n, int m) {
    return f[t] * g[t][n] % mod * g[t][m] % mod;
}

void init(lint n = 1e5) {
    for (lint i = 1; i <= n; ++i) {
        for (lint j = 1; i * j <= n; ++j)
            (f[i * j] += (mod + mob[j]) % mod * i % mod * iphi[i] % mod) %= mod;
    }

    for (lint t = 1; t <= n; ++t) {
        g[t].resize(n / t + 1);
        for (int i = 1; i * t <= n; ++i)
            g[t][i] = (g[t][i - 1] + phi[i * t]) % mod;    
    }

    for (int i = 1; i < B; ++i) for (int j = 1; j < B; ++j) {
        int len = n / max(i, j);
        t[i][j].resize(len + 2);
        t[i][j][0] = 0;
        for (int k = 1; k <= len; ++k)
            t[i][j][k] = (t[i][j][k - 1] + f[k] * g[k][i] % mod * g[k][j] % mod) % mod;
    }

    S = N / B; 
}

很烦写而已。


结构总结

在这类莫比乌斯反演中,经典的两个套路:

  • 提取公因数

  • 枚举 \(T = px\)

其实在 Pecco 的文章中,对于提取公因数这个方法有更加深刻的阐释。其不仅能应用在只有 \(i, j\) 两个变量的模型中,还可以扩展到更多的变量上。

再次膜拜大佬:# 算法学习笔记(36): 莫比乌斯反演


其实一般讲莫比乌斯反演到这里就没有了,但是我看了《离散数学》中的莫比乌斯反演一章。我发现两者根本不在同一个位阶上……这就是颠覆我认知的原因。

所以这里我还要把莫比乌斯反演扩展出来。


莫比乌斯再认识

我们考虑这么一个情况:

有集合 \(X\) 和偏序关系 \((P(X), \subseteq)\),设:

\[F : P(X) \to \R \quad G : P(X) \to \R \]

其中:\(G(S) = \sum_{T \subseteq S}F(T)\)

则可以求得:\(F(S) = \sum_{T \subseteq S}(-1)^{|S| - |T|}G(T)\)

\(G\) 求的 \(F\) 的过程称为反解,其中,\((-1)^{|S|-|T|}\) 就是莫比乌斯函数在这种情况下的取值,也称为容斥系数。

顺便回顾一下基本容斥原理:

\(A_1, A_2, \cdots, A_n\) 是有限集 \(S\) 的子集(代表 \(n\) 中属性?)定义 \(F(K)\)\(K\) 为下标集合,\(\subseteq \{1, 2, \cdots, n\}\))为集合 \(S\)\(\in A_i (i \not\in K)\) 的元素的个数。也就是对于 \(s \in S\),计数 \(s\) 当且仅当:

\[\forall i \in K, s \notin A_i \qquad \forall j \not\in K, s \in A_j \]

于是设 \(G(K) = \sum_{L \subseteq K}F(L)\)

其计数 \(S\) 中属于 \(j\) 不在 \(K\) 中的所有 \(A_j\) 的元素,以及属于其他的一些集合的元素的个数。因而还有:

\[G(K) = | \bigcap_{i \not\in K} A_i | \]

根据上文,有

\[F(K) = \sum_{L \subseteq K} (-1)^{|K| - |L|}G(L) \tag{1} \]

此时 \(F(X_n)\quad (X_n = \{1, 2, \cdots, n\})\) 计数的是那些仅属于满足 \(i \not\in X_n\) 的集合 \(A_i\) 的元素,因此:

\[F(X_n) = | \bigcap_{i \in X_n} \overline{A_i}| \]

带入 \((1)\) 中可以得到:

\[| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| = \sum_{L \subseteq X_n} (-1)^{n - |L|} | \bigcap_{i \not\in L} A_i| \]

如过等价的利用 \(L\) 的补集,那么我们有:

\[| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}| = \sum_{J \subseteq X_n} (-1)^{J} | \bigcap_{i \in J} A_i| \]

这就是基本的容斥原理。


二项式反演

为什么突然到这里了……

二项式反演可以说是上面内容的一种特殊形式。其满足:

\[|S| = |T| \implies F(S) = F(T), G(S) = G(T) \]

此时我们可以直接通过集合大小表示:\(F(S) = f(|S|), G(S) = g(|S|)\)

于是对于 \(G(K) = \sum_{L \subseteq K} F(L)\),合并相同大小的子集,即可得到:

\[g(k) = \sum_{l = 0}^{k} {k \choose l} f(l) \]

根据反演,也就有:

\[f(k) = \sum_{l = 0}^k (-1)^{k - l} {k \choose l} g(l) \]

这也就是二项式反演在此的推导,这里的莫比乌斯函数 \(\mu\),后文再说。


扩展到偏序集

在此,我们扩展到任意有限偏序集 \((X, \le)\)。不过为了得到莫比乌斯函数,我们首先考虑二元变量。

\(\mathbb{F}(X)\) 是满足只要 \(x \not \le y\) 就有 \(f(x, y) = 0\) 的所有实数函数的集合。

\[f: X \times X \to \R \]

我们如此定义卷积 \(h = f * g\)

\[h(x, y) = \begin{cases} \sum_{\{z: x \le z \le y\}} f(x, z)g(z, y) & (x \le y) \\ 0 & otherwise \end{cases} \]

不难证明卷积满足结合律,这部分留个读者思考。

于是,我们重新定义如下函数:

  • 单位函数(克罗内克 delta 函数):

\[\delta(x, y) = \begin{cases} 1 & \text{if } x = y \\ 0 & \text{otherwise } \end{cases} \]

  • 常数函数(zeta function):

\[\zeta(x, y) = \begin{cases} 1 & \text{if } x \le y \\ 0 & \text{otherwise} \end{cases} \]

至于莫比乌斯函数,与上文的定义类似,也就是 \(\zeta\) 的逆函数:

\[\mu * \zeta = \delta \]

于是通过卷积的定义,我们得到:

\[\sum_{\{z: x \le z \le y\}} \mu(x, z)\zeta(z, y) = \delta(x, y) \qquad (x \le y) \]

或等价的:

\[\sum_{\{z: x \le z \le y\}} \mu(x, z) = \delta(x, y) \qquad (x \le y) \tag{2.1} \]

而等式 \((2.1)\) 意味着,对于所有的 \(x\):

\[\mu(x, x) = 1 \]

以及:

\[\mu(x, y) = -\sum_{\{z: x \le z \lt y\}} \mu(x, z) \qquad (x < y) \]

至于莫比乌斯反演,无非还是:

\[f * \zeta = g \iff f = g * \mu \]


于是我们重新思考二项式反演,其实就是偏序集 \((P(X_n), \subseteq)\) 上的莫比乌斯反演。

\(A\)\(B\)\(X_n\) 的子集,且 \(A \subseteq B\),有 \(\mu(A, B) = (-1)^{|B| - |A|}\)

这可以通过归纳假设证明,这里不过多展开。


开篇讲的狄利克雷卷积上的莫比乌斯反演,其实就是偏序集 \((\Z, |)\) 上的莫比乌斯反演。

这东西谁都知道,一元的莫比乌斯函数 \(\mu(x)\) 怎么求。不过我们的目标是计算该偏序集的 \(\mu(a, b)\)

但是,由于如果 \(a | b\)\(\mu(a, b) = \mu(1, \frac ba)\)。所以我们只需要算 \(\mu(1, x)\) 即可。

\(\mu(x)\) 其实就是 \(\mu(1, x)\) ……


考虑离散傅立叶变换。

越扯越远了……QwQ

不了解离散傅立叶变换的可以参考:算法学习笔记(17): 快速傅里叶变换(FFT)

我们不是有:

\[h(\omega^x) = \sum_{k = 0}^{n - 1} c_k \omega^{kx} \]

我们整理一下重新写出:

\[g(x) = \sum_{k = 0}^{n - 1} \omega^{kx} f(k) \]

根据离散傅立叶逆变换,则有:

\[f(x) = \frac 1n \sum_{k = 0}^{n - 1} \omega^{-kx} g(k) \]

其中,\(\frac 1n \omega^{-kx}\) 就是容斥系数,\(\mu(k, x)\)


最后的最后,提一个题吧:[春季测试 2023] 幂次 - 洛谷

其实也可以通过容斥(求 \(\mu\))求解,但并非反演。

参见博客:幂次 - Jijidawang

与算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演相似的内容:

算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演

# 狄利克雷卷积和莫比乌斯反演 > 看了《组合数学》,再听了学长讲的……感觉三官被颠覆…… [TOC] ## 狄利克雷卷积 如此定义: $$ (f*g)(n) = \sum_{xy = n} f(x)g(y) $$ 或者可以写为 $$ (f * g)(n) = \sum_{d | n} f(d) g

算法学习笔记(6): 树链剖分

树链剖分 树链剖分是一个很神奇,但是在树上可以完成一些区间操作问题 简单来说,就是把一棵树分成一条条的链,通过维护链上的信息来维护整棵树的信息 基础知识可以参考我的另外一篇博客:算法学习笔记(5): 最近公共祖先(LCA) 这里假设你已经掌握了上述博客中的所有相关知识,并清晰了其背后的原理 性质?发

算法学习笔记(11): 原根

原根 此文相对困难,请读者酌情食用 在定义原根之前,我们先定义其他的一点东西 阶 通俗一点来说,对于 $a$ 在模 $p$ 意义下的阶就是 $a^x \equiv 1 \pmod p$ 的最小正整数解 $x$ 或者说,$a$ 在模 $p$ 意义下生成子群的阶(群的大小) 再或者说,是 $a$ 在模

算法学习笔记(30):Kruskal 重构树

Kruskal 重构树 这是一种用于处理与最大/最小边权相关的一个数据结构。 其与 kruskal 做最小生成树的过程是类似的,我们考虑其过程: 按边权排序,利用并查集维护连通性,进行合并。 如果我们在合并时,新建一个节点,其权值为当前处理的边的权值,并将合并的两个节点都连向新建的节点,那么就可以得

算法学习笔记(3.1): ST算法

ST表 在RMQ(区间最值)问题中,著名的ST算法就是倍增的产物。ST算法可以在 \(O(n \log n)\) 的时间复杂度能预处理后,以 \(O(1)\) 的复杂度在线回答区间 [l, r] 内的最值。 当然,ST表不支持动态修改,如果需要动态修改,线段树是一种良好的解决方案,是 \(O(n)\

C++算法之旅、09 力扣篇 | 常见面试笔试题(上)算法小白专用

算法学习笔记,记录容易忘记的知识点和难题。详解时空复杂度、50道常见面试笔试题,包括数组、单链表、栈、队列、字符串、哈希表、二叉树、递归、迭代、分治类型题目,均带思路与C++题解

C++算法之旅、08 基础篇 | 质数、约数

算法学习笔记,记录容易忘记的知识点和难题。试除法、分解质因数、筛质数、约数个数、约数之和、最大公约数

算法学习笔记(1): 欧几里得算法及其扩展

扩展欧几里得算法详解 在了解扩欧之前我们应该先了解欧几里得算法 欧几里得算法 这是一个递归求最大公约数(greatest common divisor)的方法 $$ gcd(a, b) = gcd(b, a % b) $$ 可以通过一个类似的简单公式推导而来 好像叫做辗转相减法来着? $$ gcd(

算法学习笔记(3): 倍增与ST算法

倍增 目录倍增查找 洛谷P2249重点变式练习快速幂ST表扩展 - 运算扩展 - 区间变式答案倍增更多的用法优化矩形查询优化建图优化 DP作者有话说 倍增,字面意思即”成倍增长“ 他与二分十分类似,都是基于”2“的划分思想 那么具体是怎么样,我们以一个例子来看 查找 洛谷P2249 依据题面,我们知

算法学习笔记(4): 并查集及其优化

# 并查集 并查集,Disjoint-Set,或者通俗一点,叫做MergeFind-Set,是一种可以动态维护若干个不重叠的集合,并支持集合之间的合并与查询的数据结构。 集体来说,并查集支持下列两个操作: - Find,查询元素所属集合 - Merge,将两个元素所属集合合并 一般来说,为了具体实现