反演笔记

反演

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

反演原理

若对于

$$f_i=\sum_{j=0}^{i}a_{i,j}g_j$$

它的反演为

$$g_i=\sum_{j=0}^{i}b_{i,j}f_j$$

那么，

$$\begin{aligned} g_i&=\sum_{j=0}^{i}b_{i,j}f_j\\ &=\sum_{j=0}^ib_{i,j}\sum_{k=0}^ja_{j,k}g_k\\ &=\sum_{j=0}^ig_j\sum_{k=j}^ia_{k,j}b_{i,k} \end{aligned}$$

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

$$\sum_{k=j}^ib_{i,k}a_{k,j}=\sum_{k=j}^ia_{i,k}b_{k,j}=[i=n]$$

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

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

二项式反演

假如我们已经知道

$$f(n)=\sum_{k=0}^{n}\binom{n}{k}g(k)$$

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

首先，我们有一个式子

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}=[n=0]$$

然后，写一句废话

$$g(n)=\sum_{m=0}^{n}[n-m=0]\binom{n}{m}g(m)$$

将上面那个式子代入

$$g(n)=\sum_{m=0}^{n} \sum_{k=0}^{n-m}(-1)^k\binom{n-m}{k}\binom{n}{m}g(m)$$

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

$$\binom{n}{m}\binom{n-m}{k}=\binom{n}{k}\binom{n-k}{m}$$

于是

$$\begin{aligned} g(n)&=\sum_{m=0}^{n}\sum_{k=0}^{n-m}(-1)^k\binom{n}{k}\binom{n-k}{m}g(m) \\ &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{m=0}^{n-k}\binom{n-k}{m}g(m)\\ &=\sum_{k=0}^{n}(-1)^k\binom{n}{k}f(n-k)\\ &=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(k) \end{aligned}$$

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

若有

$$f(n)=\sum_{k=0}^{n}\binom{n}{k}g(k)$$

则也有

$$g(n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}f(k)$$

莫比乌斯反演

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

$$f(n)=\sum_{d|k}g(d)$$

首先，我们有

$$\sum_{d|n}\mu(d)=[n=1]$$

写一句废话

$$g(n)=\sum_{m|n}[\frac{n}{m}=1]g(m)$$

然后

$$\begin{aligned} g(n)&=\sum_{m|n}[\frac{n}{m}=1]g(m)\\ &=\sum_{m|n}\sum_{d|\frac{n}{m}}\mu(d)g(m)\\ &=\sum_{d|n}\mu(d)\sum_{m|\frac{n}{d}}g(m)\\ &=\sum_{d|n}\mu(\frac{n}{d})f(d) \end{aligned}$$

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

若有

$$f(n)=\sum_{d|n}g(d)$$

则也有

$$g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)$$

矩阵形式

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

$$[m\ |\ n]\sum_{d|\frac{n}{m}}\mu(d)=[\frac{n}{m}=1]=[n=m]$$

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

$$\sum_{c|n}[m\ |\ c]\mu(\frac{c}{m})$$

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

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

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

$$\begin{aligned} x&=Ix\\ x&=(BA)x\\ x&=B(Ax)\\ x&=Bb \end{aligned}$$

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

题外话：

$$f(n)=\sum_{k=0}^{n}\binom{n}{k}g(k)$$ $$f(n)=\sum_{d|n}g(d)$$

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

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

$$f(n)=\sum_{k=1}^n a_{n,k}g(k)$$

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

那么一定满足性质

$$\sum_{k=1}^{n}a_{n,k}\mu(k,m)=[n=m]$$

这个可以递推求出。

此时答案已经很明显了：

$$g(n)=\sum_{k=1}^n \mu(n,k)f(k)$$

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

UOJ Round#5 C

$$\sum_{j = 1}^{n} \gcd(i, j)^c \cdot \text{lcm}(i, j)^d \cdot x_j \equiv b_i \pmod{p}$$

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

UOJ

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

$$\sum_{j=1}^n \gcd(i,j)^{c - d} \cdot i^d \cdot j^d \cdot x_j = b_i$$

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

$$\sum_{j=1}^n f(\gcd(i,j)) \cdot g(i) \cdot h(j) \cdot x_j = b_i$$

这个东西的关键其实在于 $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 \sum_{d}[d \mid i][d \mid j] \cdot f_r(d) \cdot g(i) \cdot h(j) \cdot x_j = b_i$$

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

$$\sum_{d \mid i} f_r(d) \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j = b_i / g(i)$$

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

$$\sum_{d \mid i} f_r(d) z_d = b_i / g(i)$$

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

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

$$z_d = \sum_{j=1}^{n} [d \mid j] \cdot h(j) \cdot x_j$$

已知左边，想求右边？还是似曾相识！我们知道

$$h(d) \cdot x_d = z_d - \sum_{j=1}^{n} [j > d][d \mid j] \cdot h(j) \cdot x_j$$

直接反演得到 $x_j$，问题解决！

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

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

#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