- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
看了《组合数学》,再听了学长讲的……感觉三官被颠覆…… 。
如此定义:
或者可以写为 。
这些函数都是积性函数,满足 \(gcd(i, j) = 1 \implies f(ij) = f(i)f(j)\) .
可能有不完整的地方…… 。
其中可以通过 \(I\) 转化的,都可以通过 \(\mu\) 转换回去。考虑 \(I * \mu = \varepsilon\) 的事实,后面会讲.
根据定义,我们有 。
即 。
根据卷积:
在 \(n = p^k\) 时( \(p\) 为质数),有:
所以 \((\varphi * I)(p^k) = p^k\) 。
将 \(n\) 质因数分解为 \(\prod p^k\) ,根据积性函数的定义,可知:
应该把后面看完了再回来看这个…… 。
莫比乌斯函数定义为:
根据: \(\varphi * I = 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\) .
所以,在 狄利克雷卷积 中:
至于为什么强调狄利克雷卷积……后文会提及 。
莫比乌斯函数常用于以下形式 。
或者可以写作:
而这就是 莫比乌斯反演 的核心公式.
很简单的公式,根本无需记忆…… 。
和欧拉函数 \(\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 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]余数求和 - 洛谷 。
补充 :现在我们考虑更极端的情况,例如求:
其中:
写出来 \(n = 1e9\) 的时候可以轻松过掉。所以其复杂度呢?
膜拜 @jijidawang in 讨论 .
为 \(O(n^{\frac 34})\) ,证明见讨论.
所以见到类似的数论分块套数论分块,大胆的写下去吧! 。
其实数论分块不仅仅可以解决 \(\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)\) .
于是对于:
在这里,有一个非常经典的处理方法:提取公因数 。
也就是枚举 \(gcd(i, j)\) 。
于是最终利用 数论分块 求即可。复杂度为 \(O(n + \sqrt {\min(n, m)})\) .
但是代码需要注意,每一次取小步跳:
r = min(n / (n / l), m / (m / l));
原题: GCD SUM - 洛谷 。
于是求 \(\sum_{i = 1}^{n}\sum_{j = 1}^m \gcd(i, j)\) 的方法与结构1类似即可.
于是求 \(\sum_{x = 1}^n \sum_{y = 1}^m \tau(xy)\) 也就很简单了.
原题: YY的GCD - 洛谷 。
令 \(P\) 表示质数集合,求:
我们首先提取公因数:
于是根据模型1:
接下来是一个非常经典的套路:枚举 \(T = px\) 。
于是问题转化为求 \(\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)\) ,设:
其中: \(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| \]
这就是基本的容斥原理.
为什么突然到这里了…… 。
二项式反演可以说是上面内容的一种特殊形式。其满足:
此时我们可以直接通过集合大小表示: \(F(S) = f(|S|), G(S) = g(|S|)\) 。
于是对于 \(G(K) = \sum_{L \subseteq K} F(L)\) ,合并相同大小的子集,即可得到:
根据反演,也就有:
这也就是二项式反演在此的推导,这里的莫比乌斯函数 \(\mu\) ,后文再说.
在此,我们扩展到任意有限偏序集 \((X, \le)\) 。不过为了得到莫比乌斯函数,我们首先考虑二元变量.
设 \(\mathbb{F}(X)\) 是满足只要 \(x \not \le y\) 就有 \(f(x, y) = 0\) 的所有实数函数的集合.
我们如此定义 卷积 \(h = f * g\) :
不难证明 卷积 满足 结合律 ,这部分留个读者思考.
于是,我们重新定义如下函数:
至于 莫比乌斯函数 ,与上文的定义类似,也就是 \(\zeta\) 的逆函数:
于是通过卷积的定义,我们得到:
或等价的:
而等式 \((2.1)\) 意味着,对于所有的 \(x\)
以及:
至于 莫比乌斯反演 ,无非还是:
于是我们重新思考二项式反演,其实就是偏序集 \((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) 。
我们不是有:
我们整理一下重新写出:
根据离散傅立叶逆变换,则有:
其中, \(\frac 1n \omega^{-kx}\) 就是容斥系数, \(\mu(k, x)\) .
最后的最后,提一个题吧: [春季测试 2023] 幂次 - 洛谷 .
其实也可以通过容斥(求 \(\mu\) )求解,但并非反演.
参见博客: 幂次 - Jijidawang 。
最后此篇关于算法学习笔记(24):狄利克雷卷积和莫比乌斯反演的文章就讲到这里了,如果你想了解更多关于算法学习笔记(24):狄利克雷卷积和莫比乌斯反演的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我是一名优秀的程序员,十分优秀!