谈反演和变换一

Veröffentlicht am | in

从错排开始

什么是错排？

比如一天有$n$只咸鱼要坐座位，第$i$号咸鱼并不想做第$i$号位置，问有多少种方案？

咸鱼怎么想？

  • 全部咸鱼随便排的方案数是$n!$
  • 排除有一只咸鱼坐在自己的位置$n!-\binom{n}{1}(n - 1)!$
  • 加回来两只咸鱼坐对的情况$n! - \binom{n}{1}(n - 1)! + \binom{n}{2}(n - 2)!$
  • …

所以我们得到公式？

错排的方案数$=\sum_{k = 0}^{n}(-1)^k\binom{n}{k}(n - k)!$

我们换个思路？

令$f(n)$表示$n$只咸鱼随便坐的方案数，显然$f(n)=n!$
令$g(n)$表示$n$只咸鱼不坐自己位置的方案数。
好了，我们现在来枚举有多少只咸鱼乱坐，我们就能得到：
$$f(n)=\sum_{k=0}^{n}\binom{n}{k}g(k)$$
这是什么？？？聪明的同学已经发现，这其实就是解线性方程！！
令矩阵$A$为$A_{ij}=\binom{i}{j}$，$A$是长这样的：
$$
A=
\begin{bmatrix}
\binom{0}{0} & 0 & \cdots & 0\\
\binom{1}{0} & \binom{1}{1} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots \\
\binom{n}{0} & \binom{n}{1} & \cdots & \binom{n}{n}
\end{bmatrix}
$$
这是个下三角矩阵，显然我们能够通过行变换得到其逆矩阵。
算来算去发现根本不好求逆矩阵，于是我们试着直接从$f$和$g$的关系出发，试着推导出$g$和$f$的关系。

废话一

我们首先观察一下$g$有什么性质，显然我们能找到一个废话般的性质：
$$g(n)=\sum_{k=0}^n[n=k]\binom{n}{k}g(k)$$
好像只要是个函数都会满足这个性质。。

废话二

再说一个废话
$$(1-1)^n=[n=0]$$
好像小学生都知道这个性质。。。

好了现在我们把两个废话弄到一起
就能得到:
$$g(n)=\sum_{k=0}^n(1-1)^{n-k}\binom{n}{k}g(k)$$
我们把$(1-1)^{n-k}$展开：
$$g(n)=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n-k}{j}(-1)^j\binom{n}{k}g(k)$$
两个二项式系数实际上就是说，从$n$只咸鱼中选择$k$只出来，再选$j$只的方案，我们可以先选$j$只
所以就变成了：
$$g(n)=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n}{j}(-1)^j\binom{n-j}{k}g(k)$$
两个求和是求得是倒三角的区域，所以换一换求和的顺序：
$$g(n)=\sum_{j=0}^{n}\binom{n}{j}(-1)^j\sum_{k=0}^{n-j}\binom{n-j}{k}g(k)$$
回忆$f$的表达式，我们能得到：
$$g(n)=\sum_{j=0}^{n}\binom{n}{j}(-1)^jf(n-j)$$

我们就得到了传说中的二项式反演：

若
$$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$，试图搞到一个函数$g$
其中$f(n)=\sum_{d|n}g(d)$

地球人都知道？

这就是莫比乌斯反演
通过学（chang）习（shi）我们知道，其实$g(n)=\sum_{d|n}u(\frac{n}{d})f(d)$
其中$u$表示莫比乌斯函数（就是莫比乌斯带的那个人）
但这是怎么来的呢？

废话一

$$g(n)=\sum_{k|n}[\frac{n}{k}=1]g(k)$$
是不是和二项式的废话一很像？

废话二

$$\sum_{d|n}u(d)=[n=1]$$
这个还是有点小难证的。。
是不是和二项式的废话二很像？

照着葫芦画瓢，带来带去我们就能得到莫比乌斯反演啦：
若
$$f(n)=\sum_{d|n}g(d)$$
则
$$g(n)=\sum_{d|n}u(\frac{n}{d})f(d)$$

怎么求莫比乌斯反演？

强行筛$u$

这种暴力的方法，虽然我是一直都在用，但是真的好麻烦，还要枚举约数
这里还是给出筛莫比乌斯函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void mobius() {
	memset(check, false, sizeof(check));
	mu[1] = 1;
	int tot = 0;
	for (int i = 2; i <= N; i++) {
		if (check[i]) {
			prime[++tot] = i;
			mu[i] = -1;
		}
		for (int j = 1; j <= tot; j++) {
			if (i * prime[j] > N) break;
			check[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			else
				mu[i * prime[j]] = -mu[i];
		}
	}
}

神（yu）奇（chun）的办法

其实。。问题没有那么复杂
我们观察一下$f$与$g$的关系：
$$f(n)=\sum_{d|n}g(d)=\sum_{d|n,n>d}g(d)+g(n)$$
假设我们把$d$小于$n$的$g(d)$都处理好了，那么是不是就可以得到g(n)了呢？
所以我们有如下递推得到$g$的方法：

1
2
3
4
5
for (int i = 1; i <= n; i++)
	g[i] = f[i];
for (int i = 1; i <= n; i++)
	for (int j = i + i; j <= n; j += i)
		g[j] -= g[i];

是不是短小精悍