反演的原理

反演一般是解决这样一个问题:有两个数列 $\lbrace f_n\rbrace,\lbrace g_n\rbrace$,满足关系:
$$g_n = \sum_{i=0}^n a_{ni}f_i$$
题目要你求 $f_n$,但你却知道数列 $\lbrace g_n\rbrace$ 怎么求。这时就可以利用反演,用 $g_0, g_1, \cdots, g_n$ 求出 $f_n$,即:
$$f_n = \sum_{i = 0}^n b_{ni}g_i$$

我们就考虑,如果 $\lbrace f_n\rbrace,\lbrace g_n\rbrace$ 能够反演,系数 $a,b$ 应该满足什么关系。

我们假设它们能够反演,将上面两个式子合并:
$$f_n=\sum_{i=0}^n b_{n,i}\sum_{j=0}^ia_{i,j}f_j$$

$$f_n=\sum_{i=0}^nf_i\sum_{j=i}^n b_{n,j}a_{j,i}$$

如果能够反演,那无论 $\lbrace g_n\rbrace$ 为多少,上式都应成立,因此反演的充要条件就是:
$$\sum_{j=i}^n a_{nj}b_{ji} = [i=n]$$

满足这个条件的式子有很多,而下面会提到其中的一部分。

普通容斥(子集反演)

形式一:
$$f(S)=\sum_{T\subseteq S} g(T)$$
$$g(S)=\sum_{T\subseteq S} (-1)^{|S|-|T|}f(T)$$
形式二:
$$f(S)=\sum_{S\subseteq T} g(T)$$
$$g(S)=\sum_{S\subseteq T} (-1)^{|T|-|S|}f(T)$$

1.BZOJ4455 小星星

代码链接

2.CF451 Devu and Flowers

代码链接

二项式反演

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

1.BZOJ3622 已经没有什么好害怕的了

代码链接

2.BZOJ1879 Bill的挑战

代码链接

斯特林反演

$$f(n)=\sum_{k=0}^n \begin{Bmatrix} n \ m \end{Bmatrix} g(k)$$
$$ g(n)=\sum_{k=0}^n (-1)^{n-k} \begin{bmatrix} n \ m \end{bmatrix} f(k)$$

莫比乌斯反演

形式一:
$$f(n)=\sum_{d \mid n} g(d)$$
$$g(n)=\sum_{d|n} \mu(\frac{n}{d})f(d)$$

形式二:
$$f(n)=\sum_{n \mid d} g(d)$$
$$g(n)=\sum_{n|d} \mu(\frac{d}{n})f(d)$$

1.BZOJ2301 Problem b

代码链接

2.BZOJ2820 YY的GCD

代码链接

最值反演

两种普通形式:
$$\max{S}=\sum_{T\subset S}(-1)^{|T|+1}\min{T}$$
$$\min{S}=\sum_{T\subset S}(-1)^{|T|+1}\max{T}$$

期望意义下:
$$\mathbb{E}(\max{S})=\sum_{T\subset S}(-1)^{|T|+1}\mathbb{E}(\min{T})$$

1.LOJ2542 随机游走

代码链接

发表评论

邮箱地址不会被公开。 必填项已用*标注