Tony102's Blog - 莫比乌斯反演
type: channel
link: https://tony102.com/index.php/tag/%E8%8E%AB%E6%AF%94%E4%B9%8C%E6%96%AF%E5%8F%8D%E6%BC%94/
items: CF1139D Steps to One
items: 莫比乌斯反演学习笔记

CF1139D Steps to One
type: item
date: 2021-08-20T21:46:00+08:00
description: LinkSol设 $len$ 为随机出来的一个序列长度。$$E(len) = \sum\limits_{i \geq 1} P(len = i) \times i$$$$E(len) = \sum\limits_{i \geq 1} P(len = i) \sum\limits_{j=1}^{i} 1$$$$E(len) = \sum\limits_{j \geq 1} \sum\limits_{i \geq j} P(len = i) = \sum\limits_{i \geq 1} P(len \geq i) = 1 + \sum\limits_{i \geq 1} P(len > i)$$现在来处理后面的 $\sum\limits_{i \geq 1} P(len > i)$$$P(len > i) = P((gcd_{j=1}^{i} a_i) > 1)$$阴阳师：“正难则反”$$P(len > i) = 1 - P((gcd_{j=1}^{i} a_i) = 1)$$对于序列中的每一个数，其实都可以枚举它们是 $[1,m]$ 中的哪一个，再除掉 $m^i$ 为 $i$ 个球放在 $m$ 个标有数字的盒子中，且允许有数字没出现过的总方案数。$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m} \epsilon(gcd_{j=1}^{i} a_j)}{m^i} $$对最后一层的求和符号使用莫比乌斯反演$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m}\sum_{d|(gcd_{j = 1}^{i} a_j)} \mu(d)}{m^i} $$对每一层都莫比乌斯反演，把枚举的 $d$ 提到最前面去$$lsh = 1 - \frac{\sum_{d=1}^{m} \mu(d)\sum_{a_1=1}^{m} [d|a_1] \cdots}{m^i}$$后面的部分上指标同时除以 $d$ 之后可以直接拿出来$$lsh = \frac{\sum_{d=1}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$$$lsh = 1 - \frac{\sum_{d=2}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$所以带回原式可得：$$1 - \frac{1}{m^i} \sum\limits_{i \geq 1}\sum\limits_{d=2}^{m} \mu(d)(\lfloor \frac{m}{d} \rfloor)^i$$整除分块：$$1-\sum\limits_{d = 2}^{m} \mu(d)\frac{\lfloor \frac{m}{d} \rfloor}{m - \lfloor \frac{m}{d} \rfloor}$$马老师告诉你，后面那一坨类似于杜教筛预处理即可。Code#include <bits/stdc++.h> #define int long long using namespace std; const int SIZE = 2e5 + 5; const int mod = 1e9 + 7; int m, tot; int isnPri[SIZE], pri[SIZE], mu[SIZE], inv[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (…

莫比乌斯反演学习笔记
type: item
date: 2020-11-14T16:46:00+08:00
description: 莫比乌斯函数定义定义函数 $\mu (d)$$$ \begin{equation} \mu(d)= \left\{ \begin{array}{lr} 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d=1\\ (-1)^k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d= \prod_{i=1}^{k} p_i \ \& \ \forall i,j \in [1,k], p_i \not= p_j \\ 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall c_i \geq 2 \end{array} \right. \end{equation} $$还有一些常用的性质最常用的: $\forall n \in N, \sum_{d|n} = [n=1]$$\forall n \in N, \sum_{d|n} \frac{\mu (d)}{d} = \frac{\varphi(n)}{d}$均不会证Codeinline void getMu() { int siz = 10000000; isPrime[1] = mu[1] = 1; for (register int i = 2; i <= siz; ++ i) { if (!isPrime[i]) { prime[++ tot] = i, mu[i] = -1; } for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) { isPrime[i * prime[j]] = 1; if (i % prime[j]) mu[i * prime[j]] = -mu[i]; else { mu[i * prime[j]] = 0; break; } } } }莫比乌斯反演定理设两个单元函数 $F(x)$ , $f(x)$ 分别为$$ F(x) = \sum_{d\mid n} f(d) $$那么$$ f(x) = \sum_{d|n} \mu(d) F(\lfloor \frac{n}{d} \rfloor) $$Summary其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了基本的东西做几个题就会了