反演
对于 $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$。
由小学奥数我们知道这个东西就是
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 |
|
参考
ICPC Camp 2015 炫酷反演魔术 - vfk