什么是反演

  对于数列\(\left\{f_n\right\}\)以及数列\(\left\{g_n\right\}\)满足

\[g_n=\sum_{i=0}^na_{ni}f_i \tag{1}\]

  反演便是利用\(\left\{g_n\right\}\)反推出\(\left\{f_n\right\}\), 也即

\[f_n=\sum_{i=0}^nb_{ni}g_i \tag{2}\]

  本质上来说这是一个反解线性方程组的过程, 但观察后会发现整个方程组是一个下三角矩阵, 可以思考出更加快捷的方法

反演原理

  为了便于后面的叙述, 首先引入\(\delta(i,j)\)函数\((Kronecker's\ delta)\), 它的定义为

\[\delta\left(i,j\right)=\begin{cases}1\quad i=j\\0\quad i\neq j\end{cases}\qquad(\text{也可记为}[i=j])\]

  下面考虑反演的过程, 考虑下面的式子应该满足什么条件

\[ \sum_{i=0}^nb_{ni}g_i=f_n \tag{3} \]

\[ \begin{array}{l} LHS&=&\displaystyle\sum_{i=0}^nb_{ni}g_i\\ &=&\displaystyle\sum_{i=0}^nb_{ni}\sum_{j=0}^ia_{ij}f_j\\ &=&\displaystyle\sum_{i=0}^nf_i\sum_{j=i}^nb_{nj}a_{ji} \end{array} \]

  为了便于理解最后一步, 我们用矩阵进行表示

\[ \begin{bmatrix} b_{n0}a_{00}f_0\\ b_{n1}a_{10}f_0 & b_{n1}a_{11}f_1\\ b_{n2}a_{20}f_0 & b_{n2}a_{21}f_1 & b_{n2}a_{22}f_2\\ \vdots & \vdots & \ddots \\ b_{nn}a_{n0}f_0 & b_{nn}a_{n1}f_1 & \cdots & b_{nn}a_{nn}f_n \end{bmatrix} \]

  前一个是对行进行, 再将行加起来, 后一个是对列进行, 再将列加起来

  因此, 式\((3)\)成立的条件等价于

\[\sum_{j=i}^nb_{nj}a_{ji}=\delta(n,i) \tag{4}\]

  同理, 将\(f\)代入带\(g\)的求和式中, 可以推出

\[\sum_{j=i}^na_{nj}b_{ji}=\delta(n,i) \tag{5}\]

  如果某个数列满足上面的条件, 我们便阔以利用反演公式

二项式反演

原理

  二项式反演\((binomial\ inversion)\)在容斥中经常用到, 可以表示为

\[ f_n=\sum_{i=0}^n\left(-1\right)^n\begin{pmatrix}n\\i\end{pmatrix}g_i\Leftrightarrow g_n=\sum_{i=0}^n\left(-1\right)^n\begin{pmatrix}n\\i\end{pmatrix} f_i \tag{6} \]

  可以写成另一种常见形式

\[ f_n=\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}g_i\Leftrightarrow g_n=\sum_{i=0}^n\left(-1\right)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}f_i \tag{7} \]

证明:

\[\begin{array}{l} g_n&=&\displaystyle\sum_{i=0}^n\left(-1\right)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}f_i\\ &=&\displaystyle\sum_{i=0}^n\left(-1\right)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}\sum_{j=0}^i\begin{pmatrix}i\\j\end{pmatrix}g_j\\ &=&\displaystyle\sum_{i=0}^ng_i\sum_{j=i}^n\begin{pmatrix}n\\j\end{pmatrix}\begin{pmatrix}j\\i\end{pmatrix}\left(-1\right)^{n-j}\\ &=&\displaystyle\sum_{i=0}^ng_i\sum_{j=i}^n\begin{pmatrix}n\\i\end{pmatrix}\begin{pmatrix}n-i\\j-i\end{pmatrix}\left(-1\right)^{n-j}\\ &=&\displaystyle\sum_{i=0}^ng_i\begin{pmatrix}n\\i\end{pmatrix}\sum_{j=0}^{n-i}\begin{pmatrix}n-i\\j\end{pmatrix}\left(-1\right)^{n-i-j}\\ &=&\displaystyle\sum_{i=0}^ng_i\begin{pmatrix}n\\i\end{pmatrix}\left(1-1\right)^{n-i}\\ &=&g_n \end{array}\]

应用

  • 错位排列

  对于长度为\(n\)的序列\(\{a_i\}\), 求所有满足\(1\leq i\leq n\), 使得\(a_i\neq i\)的种类数

  一个高中生想到的常规方法可能是利用递推, 记所求为\(D_n\), \(n\)个错位排列按照第一位是\(2,3,\cdots,n\)分成\(n-1\), 每个组排列个数一样多, 考虑其中一组, 不妨设第一位为\(2\), 若第\(2\)位是\(1\),有\(D_{n-2}\)种, 否则有\(D_{n-1}\)种, 结合\(D_1=0,\ D_2=1\), 从而有

\[D_n=(n-1)(D_{n-1}+D_{n-2}) \tag{8}\] \[D_n-nD_{n-1}=-\left(D_{n-1}-(n-1)D_{n-2}\right)=\cdots=(-1)^{n-2} \tag{9}\] \[D_n=nD_{n-1}+(-1)^n=\cdots=n!\sum_{i=0}^n\frac{(-1)^i}{i!} \tag{10}\]

  回到正题, 我们有一个有意思的解法, 设\(f_i\)为恰好有\(i\)个位置是不变的排列, 那么 \[n!=\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}f_i \tag{11}\]   可以看粗其形式和反演公式很像, 令\(g_i=i!\), 有二项式反演 \[\begin{array}{l} f_n&=&\displaystyle\sum_{i=0}^n(-1)^{n-i}\begin{pmatrix}n\\i\end{pmatrix}g_i\\ &=&\displaystyle\sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!}\\ &=&n!\displaystyle\sum_{i=0}^n\frac{(-1)^i}{i!} \end{array} \]

  • 染色问题

  \(n\)个球排成一行, 有\(m\)种颜色, 每个球染一个颜色, 相邻两个球染不同颜色, 每种颜色至少使用一次, 求染色方案数

  不考虑每种颜色至少用一次这一条件, 那么答案显然是\(m(m-1)^{n-1}\), 设\(f_i\)为恰好使用\(i(i=0,1,2,\cdots,k)\)种颜色的方案数, 那么

\[m(m-1)^{n-1}=\sum_{i=0}^m\begin{pmatrix}m\\i\end{pmatrix}f_i \tag{12}\]

  经过反演得到

\[f_m=\sum_{i=0}^m(-1)^{m-i}\begin{pmatrix}m\\i\end{pmatrix}g_i \tag{13}\]

\(BZOJ2839\):集合计数

  记\(b_i\)为交集有至少\(i\)个集合的个数, 枚举\(i\)个交集后, 共有\(2^{n-i}\)个互不相同的集合, 每个集合又有选与不选两种方案, 故\(b_i=\begin{pmatrix}n\\i\end{pmatrix}2^{2^{n-i}}\), 那么我们开始演了

\[b_k=\sum_{i=k}^n\begin{pmatrix}i\\k\end{pmatrix}a_i\quad\Leftrightarrow\quad a_k=\sum_{i=k}^n(-1)^{n-k}\begin{pmatrix}i\\k\end{pmatrix}b_i\]

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;++i)
#define dec(i,l,r) for(int i=r;i>=l;--i)
#define mem(a,v) memset(a,v,sizeof(a))
const int N = 1e6, INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
template <typename T>
void read(T &x)
{
    x = 0; ll f = 1; char ch = getchar();
    while (!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) x = (x<<3) + (x<<1) + ch - '0', ch = getchar();
    x *= f;
}

ll n, k, ans;
ll fac[N], inv[N], p[N];

ll power(ll a, ll b)
{
    ll res = 1;
    for (; b; a = a * a % MOD, b >>= 1)
        if (b & 1) res = res * a % MOD;
    return res;
}

ll C(ll n, ll m)
{
    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}

int main()
{
    read(n), read(k);
    fac[0] = inv[0] = p[0] = 1;
    inc(i,1,n) fac[i] = (ll)fac[i-1] * i % MOD, p[i] = (ll)p[i-1] * 2 % (MOD - 1);
    inv[n] = power(fac[n], MOD - 2);
    dec(i,1,n-1) inv[i] = (ll)inv[i+1] * (i + 1) % MOD;
    inc(i,k,n) {
        (ans += MOD + ((i-k) & 1 ? -1 : 1) * (C(i,k) * C(n,i) % MOD * (power(2, p[n-i]) % MOD))) %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

斯特林反演

原理

  在这里, 先回顾一下斯特林数(\(dalao\)请自动忽略)

  • 第一类斯特林数

  定义: 将\(n\)个元素排成\(m\)个轮换的方法数

  从\(n-1\)的情况推过来, 要么将最后一个元素放进自身的轮换, 要么将最后一个元素放进前\(n-1\)个元素分成的\(\begin{bmatrix}n-1\\m\end{bmatrix}\)个轮换中的一个, 可以得到:

\[\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)*\begin{bmatrix}n-1\\m\end{bmatrix} \tag{14}\]

  由于\(\begin{bmatrix}n\\ k\end{bmatrix}\)是\(n\)个元素恰好包含\(k\)个轮换的排列个数, 对所有的\(k\)求和, 必然得到排列的总数

\[\sum_{k=0}^n\begin{bmatrix}n\\ k\end{bmatrix}=n! \tag{15}\]

  下面是与下降幂\(x^{\underline{n}}\)和阶乘幂\(x^{\overline{n}}\)的关系

\[x^{\underline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i \tag{16}\]

  用归纳法证明

\[\begin{array}{l} x^{\underline{n+1}}&=&(x-n)x^{\underline{n}}\\ &=&(x-n)\displaystyle\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=&\displaystyle\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^{i+1}-n\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=&\displaystyle\sum_{i=1}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}(-1)^{n-i+1}x^{i}+n\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i+1}x^i\\ &=&\displaystyle\sum_{i=0}^{n+1}\left(\begin{bmatrix}n\\i-1\end{bmatrix}+n\begin{bmatrix}n\\i\end{bmatrix}\right)(-1)^{n-i+1}x^i\\ &=&\displaystyle\sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i \end{array}\]

  类似可以证明

\[x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i \tag{17}\]

  • 第二类斯特林数

  定义: 将一个有\(n\)件物品的集合划分成\(m\)个非空子集的方法数

  从\(n-1\)的情况推过来, 要么将最后一个元素单独放一类, 要么与前\(n-1\)个元素的某个非空子集放一起, 可以得到:

\[\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m*\begin{Bmatrix}n-1\\m\end{Bmatrix} \tag{18}\]

  下面是与下降幂\(x^{\underline{n}}\)和阶乘幂\(x^{\overline{n}}\)的关系

\[m^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline{i}} \tag{19}\]

  用归纳法证明, 由于\(x*x^{\underline{i}}=x^{\underline{i+1}}+ix^{\underline{i}}\)

\[\begin{array}{l} m^{n+1}&=&m\displaystyle\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline{i}}\\ &=&\displaystyle\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline{i+1}}+\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}im^{\underline{i}}\\ &=&\displaystyle\sum_{i=1}^{n+1}\begin{Bmatrix}n\\i-1\end{Bmatrix}m^{\underline{i}}+\sum_{i=0}^{n+1}\begin{Bmatrix}n\\i\end{Bmatrix}im^{\underline{i}}\\ &=&\displaystyle\sum_{i=0}^{n+1}\left(\begin{Bmatrix}n\\i-1\end{Bmatrix}+i\begin{Bmatrix}n\\i\end{Bmatrix}\right)m^{\underline{i}}\\ &=&\displaystyle\sum_{i=0}^{n+1}\begin{Bmatrix}n+1\\i\end{Bmatrix}m^{\underline{i}} \end{array}\]

  类似可以证明

\[m^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}m^{\overline{i}} \tag{20}\]

  当然还有两个比较显然的东西

\[x^{\underline{n}}=(-1)(-x)^{\overline{n}} \tag{21}\] \[x^{\overline{n}}=(-1)(-x)^{\underline{n}} \tag{22}\]

  • 反转公式

\[\sum_{k=m}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}=[m=n] \tag{23}\]

\[\sum_{k=m}^n(-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}=[m=n] \tag{24}\]

\(proof\ 1:\)

\[\begin{array}{l} m^{\underline{n}}&=&\displaystyle\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}m^i\\ &=&\displaystyle\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}m^{\underline{j}}\\ &=&\displaystyle\sum_{i=0}^nm^{\underline{i}}\sum_{j=i}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}\begin{Bmatrix}j\\i\end{Bmatrix} \end{array}\]

\(proof\ 2:\)

\[\begin{array}{l} m^n&=&\displaystyle\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline{i}}\\ &=&\displaystyle\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}m^j\\ &=&\displaystyle\sum_{i=0}^nm^i\sum_{j=i}^n(-1)^{n-j}\begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\i\end{bmatrix} \end{array}\]

  • 斯特林反演

\[f(n)=\sum_{i=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k) \quad\Leftrightarrow\quad g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k) \tag{25}\]

  \((25)\)的证明如下:

\[\begin{array}{l} f(n)&=&\displaystyle\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\\ &=&\displaystyle\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{j=0}^k(-1)^{k-j}\begin{bmatrix}k\\j\end{bmatrix}f(j)\\ &=&\displaystyle\sum_{k=0}^n\sum_{j=k}^n\begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\k\end{bmatrix}(-1)^{j-k}f(k)\\ &=&\displaystyle\sum_{k=0}^n[k=n]f(k)\\ &=&f(n) \end{array}\]

莫比乌斯反演

积性函数

  函数 \(f(n)\) 满足 \(f(1)=1,\forall x,y\in \mathbb{N}^*,\gcd(x,y)=1\) 有 \(f(xy)=f(x)f(y)\)，\(f(n)\) 为积性函数。

  仅去掉条件 \(\gcd(x,y)=1\) 仍有 \(f(xy)=f(x)f(y)\)，则 \(f(n)\) 为完全积性函数。

性质

若 \(f(x)\) 和 \(g(x)\) 均为积性函数，下列函数也为积性函数:

\[f(x^p),\ f^p(x),\ f(x)g(x),\ \sum_{d|x}f(d)g(\frac{x}{d})\]

设 \(x=\prod p_i^{k_i}\)

若 \(F(x)\) 为积性函数，则有 \(F(x)=\prod F(p_i^{k_i})\)

若 \(F(x)\) 为完全积性函数，则有 \(F(x)=\prod F(p_i)^{k_i}\)

一些例子

  • 单位函数 \(\varepsilon(n)=[n=1]\) (完全积性)
  • 恒等函数 \(\operatorname{id}_k(n)=n^k\operatorname{id}_1(n)\) 通常简记为 \(\operatorname{id}(n)\) (完全积性)
  • 常数函数 \(1(n)=1\) (完全积性)
  • 除数函数 \(\displaystyle\sigma_k(n)=\sum_{d|n}d^k\sigma_0(n)\) 通常简记为 \(\operatorname{d}(n)\) 或 \(\tau(n)\)，\(\sigma_1(n)\) 通常简记作 \(\sigma(n)\)
  • 欧拉函数 \(\displaystyle\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]\)
  • 莫比乌斯函数 \(\displaystyle\mu(n)=\begin{cases}1\quad n=1,\\(-1)^k\quad n=p_1p_2\cdots p_k,\\0\quad otherwise\end{cases}\)，\(p_i\) 为互异素数

Dirichlet 卷积

定义 两个数论函数的 Dirichlet 卷积

\[(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]

性质

  • 交换律 \(f*g=g*f\)
  • 结合律 \((f*g)*h=f*(g*h)\)
  • 分配律 \(f*(g+h)=f*g+f*h\)
  • \(f*\varepsilon=f\)，其中 \(\varepsilon\) 为 Dirichlet 卷积的单位元

一些例子

\[\varepsilon=\mu*1\Leftrightarrow\varepsilon(n)=\sum_{d|n}\mu(d)\] \[d=1*1\Leftrightarrow d(n)=\sum_{d|n}1\] \[\sigma=\operatorname{id}*1\Leftrightarrow\sigma(n)=\sum_{d|n}d\] \[\varphi=\mu*\operatorname{id}\Leftrightarrow\sum_{d|n}d\cdot\mu(\frac{n}{d})\]

原理

  莫比乌斯函数\(\mu(m)\) 对所有整数\(m\geq1由等式\)

\[\sum_{d|m}\mu(d)=\left[m=1\right] \tag{26}\]

来定义, 这个等式是一个递归式, 代入\(m=1,2,\cdots,12\)可以得到前\(12\)个值:

\(m\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\)
\(\mu(m)\) \(1\) \(-1\) \(-1\) \(0\) \(-1\) \(1\) \(-1\) \(0\) \(0\) \(1\) \(-1\) \(0\)

\[g(m)=\sum_{d|m}f(d)\quad\Leftrightarrow\quad f(m)=\sum_{d|m}\mu(\frac{m}{d})g(d) \tag{27}\]

  \((27)\)的证明如下: \[\begin{array}{l} g(m)&=&\displaystyle\sum_{d|m}f(d)\\ &=&\displaystyle\sum_{d|m}\sum_{k|d}\mu(\frac{d}{k})g(k)\\ &=&\displaystyle\sum_{k|m}g(k)\sum_{d|m,k|d}\mu(\frac{d}{k})\\ &=&\displaystyle\sum_{k|m}g(k)\sum_{d|(m/k)}\mu(d)\\ &=&\displaystyle\sum_{k|m}[m/k=1]g(k)\\ &=&g(m) \end{array}\]

  若 d 包含平方因子，则 \(\mu(d)=0\)

  若 d 不包含平方因子，即\(p=p_1p_2\cdots p_k\)，\(p_i\) 均为互异素数，则 \(\mu(d)=(-1)^k\)

  \(\forall n\in\mathbb{N}^*\)，有 \(\displaystyle\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\)

线性筛求莫比乌斯函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void init() {
    memset(vis, 0, sizeof(vis));
    mu[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) { 
            prime[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * prime[j] < N; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}