0%

浅析各类反演

Rt,博主是个大菜鸡,有什么问题尽管提出。


反演的基本概念

当有这么一个式子的时候:

并且这个 $\mu$ 还很常见,那有一定概率就可以反演。

反演就是,你找出另一个函数 $a$,使得

我们不妨探寻一下这两个表达式间的规律:

接着引入艾弗森括号的概念,即 $[a]$ 这个东西表示若 $a$ 为真,则为 $1$,否则为 $0$。

容易发现,当后面那坨红的恰好等价于 $[n = d]$ 的时候,这个反演的式子就对了。

然后你冷静一下,发现 $a$ 本质上就是 $\mu$ 矩阵的逆矩阵。所以少数情况下你可以打一个 $\mu$ 的表,然后矩阵求逆求出来 $a$,观察到一定规律。

不过鉴于我不会矩阵求逆,并且也没做到那样的题,就先不写了,到时候遇到了再写。


二项式反演

首先有一个前置知识,二项式定理。

组合意义比较显然,就是每个括号决策一下,就不细究了。

然后还有就是 $0^n$ 这个东西显然就是艾弗森括号,想一想能不能通过上面那个东西搞出来 $0^n$?显然是可以的。我们代入 $a = 1, b = -1$,可以得到下面这个式子:

然后我们本质上就是用和式造出来了一个艾弗森括号,于是就可以搞这样一类反演式子:

推这种式子有一个技巧,就是令 $g_n = \sum_{d} [n = d] g_d$,然后探索出一些牛逼的东西。里面那个东西可以变成 $[n - d = 0]$ ,比如说这个例子:

wee,整完了。

再来一个对称美的式子:

证明的话。。。好像把系数拎出来,整一下就ok了。


子集反演

其实道理都是异曲同工的。

首先考虑上面我们推得的二项式艾弗森括号,如何把他推广到子集中?

从展开角度来讲,就是

这里 $ = 0$ 代表空集。

为什么有这个式子?你可以理解为,上面的二项式反演就是对这个式子算贡献。

所以,我们就可以利用这样的思路解决子集反演:

同样的,还是用那个套路:

两个红色式子都比较重要,不过不难推导。

当然还有一个反方向的子集反演,式子很一致。


多重集反演

和上面的子集反演差不多一致,主要区别在于集合变成了多重集,枚举集合变成了枚举本质不同的集合

很自然的想到:如何把多重集反演变成子集反演?只需要设计一个 $\mu(S)$ 函数,设 $S$ 包含相同元素时为 $0$ ,否则为 $(-1)^S$,然后就又变成了上面的情况。

然后类似于上面的反演,就有


莫比乌斯反演

和多重集反演完全一致,就是一个在唯一分解上的多重集反演。

这里注意,基本上所有反演子集和反演超集都是对称的。所以还有这么一个莫比乌斯反演式子(比较不常见):


莫比乌斯反演小题

Crash的数字表格:

(默认 n <= m)
推,就硬推。

注意 $calc$ 是 $1 + 2 + … + x$。

然后继续整活,设 $dt = T$ ,换掉,这一步的目的是让后面的calc能够整除分块:

你发现这题如果你能快速算出后面那坨,你就会像ei一样直接把这个题秒掉。

事实上的确是可以的,就是一个 $\text{Dirichlet}$ 前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 10001000;
const int mod = 20101009;
const int inv2 = 10050505;
template<class T> T add(T a, T b) { return a + b >= mod ? a + b - mod : a + b; }

ll calc(int x) { return (ll)x * (x+1) % mod * inv2 % mod; }
bool np[N];
int prime[N], cnt, mu[N], prefix[N], ans[N], n, m;
void init(int sz) {
mu[1] = 1, np[1] = 1;
F(i, 2, sz) {
if (!np[i]) prime[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * prime[j] <= sz; ++j) {
np[i * prime[j]] = 1;
if (i % prime[j]) mu[i * prime[j]] = -mu[i];
else { mu[i * prime[j]] = 0; break; }
}
}
F(i, 1, sz) ans[i] = (mu[i] * i % mod + mod) % mod;
F(i, 1, cnt)
for(int j = 1; prime[i] * j <= sz; ++j)
ans[j * prime[i]] = add(ans[j * prime[i]], ans[j]);
}
void solve() {
cin >> n >> m;
if (n > m) swap(n, m);
init(m);
ll answer = 0;
F(T, 1, n)
answer = add(answer, (ll)T * calc(n/T) % mod * calc(m/T) % mod * ans[T] % mod);
cout << answer << endl;
}

懒得改成根号版本了,反正就几行的事情。

欧拉心算:求

推,就硬推。

啊哈!后面的东西是个卷积!然后你就令人窒息的发现你不会了。

这里有一个性质:一个能筛的函数和 $\mu,\phi$ 卷一下,仍然能筛。所以搞一下后面那个函数即可。

upd: 来表演一下不欧拉筛, $O(n \log n)$ 过这个题。

upd: flag倒了,时限卡的太死了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define F(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define endl '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


const int N = 10000010;
int mu[N], phi[N], prime[N], cnt;
ll sum[N];
bool nprime[N];
void init() {
nprime[1] = 0;
mu[1] = phi[1] = 1;
F(i, 2, N-1) {
if (!nprime[i]) prime[++cnt] = i, mu[i] = -1, phi[i] = i - 1;
for(int j = 1; j <= cnt && i * prime[j] < N; ++j) {
nprime[i * prime[j]] = 1;
if (i % prime[j]) mu[i * prime[j]] = -mu[i], phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
mu[i * prime[j]] = 0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
F(i, 1, N-1)
for(register int j = i, val = 1; j <= N-1; j += i, ++val)
sum[j] += phi[i] * mu[val];
F(i, 1, N-1) sum[i] += sum[i - 1];
}



void solve() {
int n;
cin >> n;
ll ans = 0;
for(int l = 1, r; l <= n; l++) {
r = n / (n / l);
ans += (sum[r] - sum[l-1]) * (n/l) * (n/l);
l = r;
}
cout << ans << endl;
}

int main() {
ios::sync_with_stdio(false);
cout << fixed;

#ifdef LOCAL
double cl = clock();
#endif

init();
int T = 1;
cin >> T;
while (T--) solve();

#ifdef LOCAL
cerr << "Time elapsed: " << (clock() - cl) / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}