0%

反演笔记

反演

对于 $f(n)=\sum_{k}a_{n,k}g(k)$,已知 $f$ 求 $g$ 的过程就称为反演。

反演原理

若对于

它的反演为

那么,

我们发现,反演成立的充要条件就是

也就是说,若发现有上述式子成立,那么便可以建立起反演公式。

若把 $f$ 和 $g$ 都写成矩阵的形式,那么会发现,$f$ 与 $g$ 互为逆矩阵。反演的过程其实就是求逆矩阵的过程。

二项式反演

假如我们已经知道

以及 $f(n)$,我们想要求出 $g(n)$ 高斯消元

首先,我们有一个式子

然后,写一句废话

将上面那个式子代入

根据组合数的性质,我们知道

于是

这样,我们空手套白狼得到了二项式反演:

若有

则也有

莫比乌斯反演

让我们用同样的方法研究如下式子

首先,我们有

写一句废话

然后

我们便得到了莫比乌斯反演:

若有

则也有

矩阵形式

vfk 告诉我们,我们在上面真正用到的是这个东西

令 $c=md$,左边可以写成这样

令 $A_{c,n}=[c | n]$,$B_{m,c}=[m | c]\mu(\frac{c}{m})$

刚才的结论就是 $BA=I$

刚才解 $Ax=b$ 的推导过程就是:

其实整个过程相当于找 $A$ 的逆矩阵 $B$,也就是那个神奇的性质$\sum_{d|n}\mu(d)=[n=1]$。

题外话:

它们都是下三角矩阵,那逆矩阵。。直接 $O(n^2)$ 消元?

对于 $k\leq n$ 的一般情况:

我们算出每个 $f(m)$ 对答案的贡献,对于每一个 $m$ 我们求出 $f(m)=1$ 而其他 $f$ 都是 $0$ 的情况下的 $g$ 就行了,用 $\mu(n,m)$ 来表示这个解。

那么一定满足性质

这个可以递推求出。

此时答案已经很明显了:

然而这并没有什么用。。这里的 $\mu$ 其实就是逆矩阵,$\mu$ 一般也是比较难求的。。

UOJ Round#5 C

给出 $n,c,d,b_i$,求出 $x_i$。

UOJ

由小学奥数我们知道这个东西就是

vfk 告诉我们,这样的东西都可做

这个东西的关键其实在于 $f(\gcd(i,j))$,如果我们有一个函数 $f_r(n)$ 满足 $f(n)=\sum_{d|n}f_r(d)$ 就好做了。这个其实就是通过枚举因数 $d$ 来去掉讨厌的 $\gcd$。

在这里,直接用递推便可以求出 $f_r(n)$。因为 $f_r(n)=f(n)-\sum_{d|n\text{且}d\neq n}f_r(d)$,所以就能直接递推了。

于是我们就能写出这样的等式:

然后我们交换一下求和符号

仔细观察,发现 $\sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j$ 的意思是把所有 $j$ 是 $d$ 的倍数的 $h(j)\cdot x_j$ 加起来。反正这个只跟 $d$ 的值有关,我们记为 $z_d$。于是我们得到:

现在我们已知右边,想求左边。似曾相识?直接反演得到 $f_r(d)z_d$,然后得到 $z_d$。

但是 $z_d$ 并不是最终的答案。回忆 $z_d$ 的表达式:

已知左边,想求右边?还是似曾相识!我们知道

直接反演得到 $x_j$,问题解决!

当然,上面三个反演也可以不用递推,直接大力筛 $\mu$ 然后用狄利克雷卷积算。可谁又愿意这样写呢?

由于中间过程涉及了除法,所以就会带来无解和多解的情况。$f_r(d)$ 可能没有逆元。这种情况假如 $f_r(d)z_d\neq0$ 那么显然无解,如果 $f_r(d)z_d=0$ 就有多组解,我们把 $z_d$ 随便附个值比如让 $z_d=0$ 就好了。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 300000 + 5;
const int mod = 998244353;

int n, q;
LL c, d, b[N], mi;
LL f[N], g[N], h[N], f_r[N], f_z[N], z[N], hx[N];

LL qpow(LL a, LL b)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}

LL inv(LL x)
{
return qpow(x, mod - 2);
}

int main()
{
scanf("%d%lld%lld%d", &n, &c, &d, &q);
mi = ((c - d) % (mod - 1) + (mod - 1)) % (mod - 1);
for (int i = 1; i <= n; i++)
{
f[i] = qpow(i, mi);
g[i] = qpow(i, d);
h[i] = qpow(i, d);
}
for (int i = 1; i <= n; i++) f_r[i] = f[i];
for (int i = 1; i <= n; i++)
for (int j = i + i; j <= n; j += i)
f_r[j] = ((f_r[j] - f_r[i]) % mod + mod) % mod;
while (q--)
{
// init();
for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);

for (int i = 1; i <= n; i++) f_z[i] = b[i] * inv(g[i]) % mod;
for (int i = 1; i <= n; i++)
for (int j = i + i; j <= n; j += i)
f_z[j] = ((f_z[j] - f_z[i]) % mod + mod) % mod;
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (!f_r[i])
{
if (f_z[i])
{
ans = -1;
break;
}
z[i] = 0;
}
z[i] = f_z[i] * inv(f_r[i]) % mod;
}
if (ans == -1)
{
puts("-1");
continue;
}
for (int i = 1; i <= n; i++) hx[i] = z[i];
for (int i = n; i >= 1; i--)
for (int j = i + i; j <= n; j += i)
hx[i] = ((hx[i] - hx[j]) % mod + mod) % mod;
for (int i = 1; i <= n; i++)
{
LL x = hx[i] * inv(h[i]) % mod;
printf("%lld ", x);
}
printf("\n");
}
return 0;
}

参考

ICPC Camp 2015 炫酷反演魔术 - vfk

反演魔术:反演原理及二项式反演 - miskcoo