容斥原理与各种奇怪反演学习笔记
容斥原理与各种奇怪反演学习笔记
闲话
发现我这部分学的不咋样，于是来补课。
本文中预计涉及到的内容有：经典容斥原理、莫比乌斯反演（广义和狭义）、子集反演、二项式反演。
容斥原理
引入
我们用一个很简单的数学题来引入对容斥原理的讨论。
在 \(1\sim 20\) 中，有多少整数既不是 \(3\) 的倍数，又不是 \(5\) 的倍数？
你当然可以数一遍，但是如果不是 \(20\)，而是 \({10}^{1000}\)，那就显然不行了。
小学奥数告诉我们：正难则反是一个很重要的思想。“既不是 \(3\) 的倍数，又不是 \(5\) 的倍数”不好统计，我们反过来统计“是 \(3\) 的倍数，或是 \(5\) 的倍数”。
不难发现 \(3\) 的倍数共 \(\left\lfloor\dfrac{20}{3}\right\rfloor=6\) 个，\(5\) 的倍数共 \(\left\lfloor\dfrac{20}{5}\right\rfloor=4\) 个，那是不是意味着“是 \(3\) 的倍数，或是 \(5\) 的倍数”的数有 \(6+4=10\) 个呢？并不是，因为 \(15\) 既是 \(3\) 的倍数，也是 \(5\) 的倍数，被算重了，实际上应该是 \(\left\lfloor\dfrac{20}{3}\right\rfloor+\left\lfloor\dfrac{20}{5}\right\rfloor-\left\lfloor\dfrac{20}{15}\right\rfloor=9\) 个。然后我们取补集，得到答案为 \(11\)。
看到这里你已经会了容斥原理，下面来形式化地写一下。
德摩根定律
我们记集合 \(A\) 的补集为 \(\overline{A}\)，则有如下性质：
- \(\overline{A\cup B}=\overline{A}\cap\overline{B}\)。
- \(\overline{A\cap B}=\overline{A}\cup\overline{B}\)。
- \(\overline{\bigcup A_i}=\bigcap\overline{A_i}\)。
- \(\overline{\bigcap A_i}=\bigcup\overline{A_i}\)。
证明很简单，对前两条讨论一个元素是否在 \(A\) 以及 \(B\) 中，然后利用前两条推后两条即可。
容斥原理
设集合 \(S\) 有 \(m\) 条性质 \(P_1\sim P_m\)，记 \(S\) 中有性质 \(P_i\) 的元素为集合 \(A_i\)，则集合中至少具有一条性质的元素个数可用下式表达：
\[\left|\bigcup A_i\right|=\sum|A_i|-\sum|A_i\cap A_j|+\sum|A_i\cap A_j\cap A_k|-\cdots+{(-1)}^{m+1}\left|\bigcap A_i\right| \]记 \(A=\{A_i\mid 1\le i\le m\}\)，则上式又可以写作：
\[\left|\bigcup A_i\right|=\sum\limits_{B\subseteq A}{(-1)}^{|B|+1}\left|\bigcap\limits_{b\in B} b\right| \]证明：
对于 \(x\in\bigcup A_i\)，设 \(x\) 出现在 \(k\) 个不同的集合 \(A_i\) 中，则 \(x\) 在容斥原理中的系数为：
\[\begin{aligned} &\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-\cdots+{(-1)}^{k+1}\binom{k}{k}\\ =&1-\binom{k}{0}+\binom{k}{1}-\binom{k}{2}+\binom{k}{3}-\cdots+{(-1)}^{k+1}\binom{k}{k}\\ =&1-\left(\binom{k}{0}-\binom{k}{1}+\binom{k}{2}-\binom{k}{3}+\cdots+{(-1)}^k\binom{k}{k}\right)\\ =&1-{(1-1)}^k\\ =&1 \end{aligned} \]证毕。
单点求欧拉 \(\varphi\) 函数
欧拉 \(\varphi\) 函数的定义是 \(\varphi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]\)。
设 \(n=\prod {p_i}^{a_i}\)，则由容斥原理有：
\[\begin{aligned} \varphi(n)&=n-\sum\left\lfloor\dfrac{n}{p_i}\right\rfloor+\sum\left\lfloor\dfrac{n}{p_ip_j}\right\rfloor-\sum\left\lfloor\dfrac{n}{p_ip_jp_k}\right\rfloor+\cdots\pm\left\lfloor\dfrac{n}{\prod p_i}\right\rfloor\\ &=n\prod\left(1-\dfrac{1}{p_i}\right) \end{aligned} \]这就是单点求欧拉函数的原理。
错排问题 \(D_n\)
记 \(A_i\) 为 \(i\) 仍在 \(i\) 位置上的全排列集合，则 \(|A_i|=(n-1)!\)，\(|A_i\cap B_i|=(n-2)!\)，以此类推。
则答案 \(D_n\) 可以写作：
\[\begin{aligned} D_n&=\left|\bigcap\overline{A_i}\right|\\ &=\left|\overline{\bigcup A_i}\right|\\ &=n!-\left|\bigcup A_i\right|\\ &=n!-\sum\limits_{i=1}^n{(-1)}^{i+1}\binom{n}{i}(n-i)!\\ &=n!\left(1+\sum\limits_{i=1}^n{(-1)}^i\dfrac{1}{i!}\right)\\ &=n!\sum\limits_{i=0}^n\dfrac{{(-1)}^i}{i!} \end{aligned} \]一些简单题
- The Lottery
- NGM2 - Another Game With Numbers
NGM2 的 AC 代码：
// Problem: SP6285 NGM2 - Another Game With Numbers
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP6285
// Memory Limit: 1500 MB
// Time Limit: 247 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 20;
ll n, k, a[N], ans;
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
int main() {
scanf("%lld%lld", &n, &k);
rep(i, 0, k-1) scanf("%lld", &a[i]);
rep(sta, 0, (1LL<> i) & 1) {
now /= __gcd(now, a[i]);
now *= a[i];
if(now > n) break;
}
}
ll mult = (__builtin_popcountll(sta) & 1) ? -1 : 1;
ans += mult * (n / now);
}
printf("%lld\n", ans);
return 0;
}
容斥系数为狭义莫比乌斯 \(\mu\) 函数的题
- SQFREE - Square-free integers
- 完全平方数
其实也就是容斥原理的应用，只不过系数比较有特点。
以 SQFREE 为例，尝试枚举因子 \(i\) 使得 \(i^2\mid n\)，手玩一下发现容斥系数与 \(i\) 的质因子个数有关，就是狭义莫比乌斯 \(\mu\) 函数，于是线性筛 \(\mu\) 函数然后整除分块求解即可。
整除分块部分按 \(n^{\frac{1}{3}}\) 分两段分析可知复杂度为 \(\mathcal{O}\left(\sqrt{n}+T\cdot n^{\frac{1}{3}}\right)\)。
放一下以前写的 AC 代码：
//By: Luogu@rui_er(122461)
#include
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e7+5;
ll T, n, tab[N], p[N], tot, mu[N], s[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
void sieve(ll lim) {
mu[1] = 1;
rep(i, 2, lim) {
if(!tab[i]) {
p[++tot] = i;
mu[i] = -1;
}
for(ll j=1;j<=tot&&i*p[j]<=lim;j++) {
tab[i*p[j]] = 1;
if(i % p[j]) mu[i*p[j]] = -mu[i];
else break;
}
}
rep(i, 1, lim) s[i] = s[i-1] + mu[i];
}
int main() {
sieve(10000000);
for(scanf("%lld", &T);T;T--) {
scanf("%lld", &n);
ll ans = 0, lim = sqrt(n);
for(ll L=1,R=0;L<=lim;L=R+1) {
R = min((ll)sqrt(n/(n/(L*L))), lim);
ans += (s[R] - s[L-1]) * (n / (L * L));
}
printf("%lld\n", ans);
}
return 0;
}
广义莫比乌斯反演
提示
【提示】这部分比较抽象，如果你的目标仅仅是做狭义莫比乌斯反演（也就是算法竞赛中常说的莫比乌斯反演）、子集反演、二项式反演的题目，或者这部分实在看不懂的话，可以选择跳过广义莫比乌斯反演部分，直接去背后面部分的公式。但是为了逻辑的完整性，我在这里写了广义莫比乌斯反演的内容。
前置知识：集合的笛卡尔积（直积）
\(X,Y\) 是集合，则 \(X\times Y=\{(x,y):x\in X,y\in Y\}\)。
例如 \(X=\{1,2\}\)，则 \(X\times X=\{(1,1),(1,2),(2,1),(2,2)\}\)。
前置知识：关系
\(X\) 是集合，则关系 \(R\subseteq X\times X\)。
对于 \((a,b)\in X\times X\)，若 \((a,b)\in R\)，记作 \(aRb\)；否则记作 \(a\not Rb\)。
关系可能有的性质：
- 自反性：\(\forall x\in X,xRx\)。
- 反自反性：\(\forall x\in X,x\not Rx\)。
- 对称性：\(\forall x,y\in X,xRy\implies yRx\)。
- 反对称性：\(\forall x,y\in X,xRy\implies y\not Rx\)。
- 传递性：\(\forall x,y,z\in X,xRy\land yRz\implies xRz\)。
前置知识：偏序、偏序集
偏序满足自反性、反对称性、传递性，例如 \(\subseteq,\leqslant,\mid\)（记作 \(\preccurlyeq\)）。
集合 \(X\) 连通在它上面定义的偏序 \(\preccurlyeq\) 为偏序集，记作 \((X,\preccurlyeq)\)。
严格偏序满足反自反性、反对称性、传递性，例如 \(\subsetneqq,<\)（记作 \(\prec\)）。
对于任意 \(x,y\in X\)，如果满足 \(xRy\) 或 \(yRx\)，则称 \(x\) 和 \(y\) 可比，否则不可比。
全序满足 \(X\) 的每一对元素在 \(R\) 的关系下都可比，例如 \(\leqslant\)。
前置知识：覆盖、哈斯（Hasse）图
设 \(a,b\in X\)，如果 \(a\prec b\) 且不存在 \(c\in X\) 使得 \(a\prec c\prec b\)，称 \(a\) 被 \(b\) 覆盖（或 \(b\) 覆盖 \(a\)），记作 \(a\prec_cb\)。
如果 \(X\) 有限，则偏序 \(\preccurlyeq\) 由覆盖关系唯一确定。
设 \((X,\preccurlyeq)\) 是偏序集，则哈斯（Hasse）图按如下方法生成：
- 如果 \(a,b\in X\) 满足 \(a\preccurlyeq b\)，将 \(a\) 画在 \(b\) 下面；如果 \(a\) 被 \(b\) 覆盖，则在 \(a\) 和 \(b\) 之间连一条边。
例如偏序集 \((\{\{1,2,3\},\{1,2\},\{1,3\},\{2,3\},\{1\},\{2\},\{3\},\varnothing\},\subseteq)\) 的哈斯（Hasse）图如下：
【还没画】
卷积
考虑有限偏序集 \((X,\preccurlyeq)\) 上的二变量函数，设 \(\mathcal F(X)\) 为只要 \(x\npreceq y\)，就有 \(f(x,y)=0\) 的所有实值函数的集合，即 \(X\times X\to\R\)。
对于 \(f,g\in\mathcal F\)，卷积 \(h=f*g\) 为
\[h(x,y)= \begin{cases} \sum\limits_{\{z:x\preccurlyeq z\preccurlyeq y\}}f(x,z)g(z,y),&x\preccurlyeq y\\ 0,&\textrm{otherwise} \end{cases} \]易证卷积有结合律 \(f*(g*h)=(f*g)*h\)（可以展开后通过交换求和顺序证明）。
特殊函数一：克罗内克 \(\delta\) 函数
\[\delta(x,y)= \begin{cases} 1,&x=y\\ 0,&x\ne y \end{cases} \]即：
\[\delta(x,y)=[x=y] \]特殊函数二：\(\zeta\) 函数
\[\zeta(x,y)= \begin{cases} 1,&x\preccurlyeq y\\ 0,&x\npreceq y \end{cases} \]即：
\[\zeta(x,y)=[x\preccurlyeq y] \]逆函数
定义函数 \(f\) 的左逆 \(g\) 满足 \(g*f=\delta\)。
则由卷积定义可知：
\[\begin{aligned} \delta(x,x)&=\sum\limits_{\{z:x\preccurlyeq z\preccurlyeq x\}}g(x,z)f(z,x)\\ &=g(x,x)f(x,x) \end{aligned} \]而 \(\delta(x,x)=[x=x]=1\)，因此：
\[g(x,x)=\frac{1}{f(x,x)} \]下面考虑 \(x\prec y\)，由卷积定义可知：
\[\delta(x,y)=\sum\limits_{\{z:x\preccurlyeq z\preccurlyeq y\}}g(x,z)f(z,y) \]把 \(g(x,y)f(y,y)\) 项移到等号左边：
\[\delta(x,y)-g(x,y)f(y,y)=\sum\limits_{\{z:x\preccurlyeq z\prec y\}}g(x,z)f(z,y) \]由于 \(x\prec y\)，所以 \(\delta(x,y)=[x=y]=0\)，因此：
\[-g(x,y)f(y,y)=\sum\limits_{\{z:x\preccurlyeq z\prec y\}}g(x,z)f(z,y) \]恒等变形得：
\[g(x,y)=-\frac{1}{f(y,y)}\sum\limits_{\{z:x\preccurlyeq z\prec y\}}g(x,z)f(z,y) \]综上，\(f\) 的左逆 \(g\) 可表示为：
\[g(x,y)= \begin{cases} \frac{1}{f(x,y)},&x=y\\ -\frac{1}{f(y,y)}\sum\limits_{\{z:x\preccurlyeq z\prec y\}}g(x,z)f(z,y),&x\prec y\\ 0,&\textrm{otherwise} \end{cases} \]同理我们定义 \(f\) 的右逆 \(h\) 满足 \(f*h=\delta\)，显然 \(g=h\)（\(g=g*(f*h)=(g*f)*h=h\)），即左逆等于右逆。
特殊函数三：\(\mu\) 函数
\(\zeta\) 的逆函数为 \(\mu\)。
考虑 \(x\preccurlyeq y\)，由逆函数定义：
\[\sum\limits_{\{z:x\preccurlyeq z\preccurlyeq y\}}\mu(x,z)\zeta(z,y)=\delta(x,y) \]或等价地，有：
\[\sum\limits_{\{z:x\preccurlyeq z\preccurlyeq y\}}\mu(x,z)=\delta(x,y) \]因此：
\[\mu(x,y)= \begin{cases} 1,&x=y\\ -\sum\limits_{\{z:x\preccurlyeq z\prec y\}}\mu(x,z),&x\prec y\\ 0,&\textrm{otherwise} \end{cases} \]广义莫比乌斯反演公式
设 \((X,\preccurlyeq)\) 是偏序集且有最小元素 \(0\)，\(\mu\) 是它的莫比乌斯函数，\(F,G:X\to\R\) 是 \(X\) 上的实值函数，则：
\[G(x)=\sum\limits_{\{z:z\preccurlyeq x\}}F(z)\iff F(x)=\sum\limits_{\{y:y\preccurlyeq x\}}G(y)\mu(y,x) \]证明如下：
设 \(A=\sum\limits_{\{y:y\preccurlyeq x\}}G(y)\mu(y,x)\)。
等量代换得：
\[A=\sum\limits_{\{y:y\preccurlyeq x\}}\sum\limits_{\{z:z\preccurlyeq y\}}F(z)\mu(y,x) \]改变 \(z\) 枚举范围：
\[A=\sum\limits_{\{y:y\preccurlyeq x\}}\sum\limits_{\{z:z\in X\}}\zeta(z,y)\mu(y,x)F(z) \]交换求和顺序：
\[A=\sum\limits_{\{z:z\in X\}}\sum\limits_{\{y:y\preccurlyeq x\}}\zeta(z,y)\mu(y,x)F(z) \]因为 \(\zeta(z,y)=[z\preccurlyeq y]\)，所以可以改变 \(y\) 枚举范围：
\[A=\sum\limits_{\{z:z\in X\}}\sum\limits_{\{y:z\preccurlyeq y\preccurlyeq x\}}\zeta(z,y)\mu(y,x)F(z) \]因为 \(\zeta*\mu=\delta\)，等量代换可得：
\[A=\sum\limits_{\{z:z\in X\}}\delta(z,x)F(z) \]因为 \(\delta(z,x)=[z=x]\)，所以得到：
\[A=F(x) \]即：
\[F(x)=\sum\limits_{\{y:y\preccurlyeq x\}}G(y)\mu(y,x) \]另一侧同理。
例子：线性有序集的莫比乌斯函数
设 \(X=\{1,2\cdots,n\}\)，有偏序集 \((X,\leqslant)\)。
则有：
\[\mu(x,x)=1 \]考虑 \(x < y\)，有：
\[\sum\limits_{\{z:x\leqslant z\leqslant y\}}\mu(x,y)=\delta(x,y) \]而 \(\delta(x,y)=[x=y]=0\)：
\[\sum\limits_{\{z:x\leqslant z\leqslant y\}}\mu(x,y)=0 \]令 \(y=x+1\)，得：
\[\mu(x,x)+\mu(x,x+1)=0 \]又因为 \(\mu(x,x)=1\)，所以：
\[\mu(x,x+1)=-1 \]令 \(y=x+2\)，同理得：
\[\mu(x,x)+\mu(x,x+1)+\mu(x,x+2)=0 \]等量代换得：
\[\mu(x,x+2)=0 \]同理，当 \(y\geqslant 2\) 时 \(\mu(x,y)=0\)。
综上：
\[\mu(x,y)= \begin{cases} 1,&y=x\\ -1,&y=x+1\\ 0,&\textrm{otherwise} \end{cases} \]有反演公式：
\[G(x)=\sum\limits_{z:z\leqslant x}F(x)\iff F(x)= \begin{cases} G(x)-G(x-1),&x\geqslant 2\\ G(0),&x=1 \end{cases} \]也就是前缀和与差分。
广义莫比乌斯反演推论：狭义莫比乌斯反演
提示
【提示】这部分比较抽象，如果你的目标仅仅是做狭义莫比乌斯反演（也就是算法竞赛中常说的莫比乌斯反演）的题目，或者这部分实在看不懂的话，可以选择跳过推导部分，直接去背后面的性质和公式。但是为了逻辑的完整性，我在这里写了狭义莫比乌斯反演的推导过程。
前置知识：偏序集的笛卡尔积（直积）
设偏序集 \((X,\preccurlyeq_1)\) 和 \((Y,\preccurlyeq_2)\)，则集合 \(X\times Y\) 上定义偏序关系 \(\preccurlyeq\)：
\[(x,y)\preccurlyeq(x^\prime,y^\prime)\iff x\preccurlyeq_1x^\prime\land y\preccurlyeq_2y^\prime \]易证 \((X\times Y,\preccurlyeq)\) 是偏序集。
推导过程
我们沿用上面的记号，同时记 \(\mu_1,\mu_2,\mu\) 为 \(X,Y,X\times Y\) 的广义莫比乌斯 \(\mu\) 函数。
可以证明 \(\mu((x,y),(x^\prime,y^\prime))=\mu_1(x,x^\prime)\mu_2(y,y^\prime)\)（其中 \((x,y),(x^\prime,y^\prime)\in X\times Y\)），具体证明过程如下：
如果 \(x\nprec x^\prime\) 或 \(y\nprec y^\prime\)，显然成立。
如果 \(x\prec x^\prime,y\prec y^\prime\)，假设 \(\forall(u,v):(x,y)\preccurlyeq(u,v)\prec(x^\prime,y^\prime)\) 都有 \(\mu((x,y),(u,v))=\mu_1(x,u)\mu_2(y,v)\)，则有：
\[\begin{aligned} \mu((x,y),(x^\prime,y^\prime))&=-\sum\limits_{(x,y)\preccurlyeq(u,v)\prec(x^\prime,y^\prime)}\mu((x,y),(u,v))\\ &=-\sum\limits_{(x,y)\preccurlyeq(u,v)\prec(x^\prime,y^\prime)}\mu_1(x,u)\mu_2(y,v)\\ &=-\sum\limits_{(x,y)\preccurlyeq(u,v)\preccurlyeq(x^\prime,y^\prime)}\mu_1(x,u)\mu_2(y,v)+\mu_1(x,x^\prime)\mu_2(y,y^\prime)\\ &=-\sum\limits_{x\preccurlyeq u\preccurlyeq x^\prime}\mu_1(x,u)\sum\limits_{y\preccurlyeq v\preccurlyeq y^\prime}\mu_2(y,v)+\mu_1(x,x^\prime)\mu_2(y,y^\prime)\\ &=0+\mu_1(x,x^\prime)\mu_2(y,y^\prime)\\ &=\mu_1(x,x^\prime)\mu_2(y,y^\prime) \end{aligned} \]证毕。
设 \(X_n=\{x:x\in[1,n]\cap\Z\}\)，考虑偏序集 \(D_n=(X_n,\mid)\) 上的广义莫比乌斯 \(\mu\) 函数，可以证明，当 \(a\mid b\) 时有 \(\mu(a,b)=\mu\left(1,\dfrac{a}{b}\right)\)，具体证明过程如下：
如果 \(a=b\)，显然成立。
如果 \(a < b\)，假设 \(\forall z:a\mid z,z < b\) 都有 \(\mu(a,z)=\mu\left(1,\dfrac{a}{z}\right)\)，记 \(z=ka\)，则有：
\[\begin{aligned} \mu(a,b)&=-\sum\limits_{a\mid z,z\mid b,z\ne b}\mu(a,z)\\ &=-\sum\limits_{a\mid z,z\mid b,z\ne b}\mu\left(1,\dfrac{a}{z}\right)\\ &=-\sum\limits_{ka\mid b,ka\ne b}\mu(1,k)\\ &=-\sum\limits_{k\mid\frac{b}{a},k\ne\frac{b}{a}}\mu(1,k)\\ &=\mu\left(1,\dfrac{a}{b}\right) \end{aligned} \]证毕。
现在只需考虑 \(a=1\) 的情况。
设 \(n=\prod {p_i}^{a_i}\)，把 \(n\) 视为 \((X_n^i=\{p_i^k:k\in[0,a_i]\cap\Z\},\mid)\) 的笛卡尔积中的元素 \((p_1^{a_1},p_2^{a_2},\cdots,p_k^{a_k})\)。
\(X_n^i\) 为线性有序集，我们已经推导过其广义莫比乌斯函数为：
\[\mu(1,p_i^{a_i})= \begin{cases} 1,&a_i=0\\ -1,&a_i=1\\ 0,&a_i\geqslant 2 \end{cases} \]因此：
\[\mu(1,n)=\prod\mu(1,p_i^{a_i})= \begin{cases} 1,&n=1\\ {(-1)}^k,&\forall i,a_i=1\\ 0,&\exists i,a_i\geqslant 2 \end{cases} \]记 \(\mu(1,n)\) 为 \(\mu(n)\)，就得到了狭义莫比乌斯函数。
狭义莫比乌斯反演公式
设 \(F,G\) 为 \(\N^+\) 上的实值函数，则有：
\[G(n)=\sum\limits_{k\mid n}F(k)\iff F(n)=\sum\limits_{k\mid n}\mu\left(\dfrac{n}{k}\right)G(k) \]狭义莫比乌斯函数性质和狄利克雷卷积
- \(\sum\limits_{d\mid n}\mu(d)=[n=1]\)。
- 若 \(\gcd(p,q)=1\)，则 \(\mu(pq)=\mu(p)\mu(q)\)（积性函数）。
- \(n=\sum\limits_{d\mid n}\varphi(d)\)。
设数论函数 \(f,g\)，则它们的狄利克雷卷积为：
\[(f*g)(n)=\sum\limits_{d\mid n}f(d)g\left(\dfrac{n}{d}\right)=\sum\limits_{d\mid n}f\left(\dfrac{n}{d}\right)g(d) \]设 \(\epsilon(n)=[n=1]\)，\(I(n)=1\)，\(id(n)=n\)，则狄利克雷卷积有如下性质：
- 满足交换律、结合律、分配律。
- 积性函数的狄利克雷卷积是积性函数。
- \(\mu*I=\epsilon\)。
- \(\varphi*I=id\)。
- \(\mu*id=\varphi\)。
狭义莫比乌斯反演应用
在算法竞赛中，狭义莫比乌斯反演常用于将 \(\epsilon(n)\) 即艾弗森约定，转化为 \(\sum\limits_{d\mid n}\mu(d)\)，然后调换合适的求和顺序以加速求解。另一个常见用途是狭义莫比乌斯 \(\mu\) 函数作为容斥系数出现，在前文容斥原理处已经提到。
相关题目见 莫比乌斯反演（函数）练习题单。
杜教筛是狄利克雷卷积的一个常见用途，但不是本文要讨论的内容，可能会写一个筛法的学习笔记并放到里面。
广义莫比乌斯反演推论：子集反演
提示
【提示】这部分比较抽象，如果你的目标仅仅是做子集反演的题目，或者这部分实在看不懂的话，可以选择跳过推导部分，直接去背后面的性质和公式。但是为了逻辑的完整性，我在这里写了子集反演的推导过程。
推导过程
接着设 \(X_n=\{x:x\in[1,n]\cap\Z\}\)，记 \(\mathcal P(X_n)=\{x:x\subseteq X_n\}\)。
设 \(A,B\in\mathcal P(X_n)\) 且 \(A\subseteq B\)，则 \(\mu(A,B)={(-1)}^{|B|-|A|}\)，证明如下：
如果 \(A=B\)，显然成立。
如果 \(A\subsetneqq B\)，假设 \(\forall C:A\subseteq C\subsetneqq B\) 都有 \(\mu(A,C)={(-1)}^{|C|-|A|}\)，设 \(p=|B\setminus A|=|B|-|A|\)，则有：
\[\begin{aligned} \mu(A,B)&=-\sum\limits_{C:A\subseteq C\subsetneqq B}\mu(A,C)\\ &=-\sum\limits_{C:A\subseteq C\subsetneqq B}{(-1)}^{|C|-|A|}\\ &=-\sum\limits_{k=0}^{p-1}{(-1)}^k\binom{p}{k}\\ &={(-1)}^p\binom{p}{p}-\sum\limits_{k=0}^p{(-1)}^k\binom{p}{k}\\ &={(-1)}^p-{(1-1)}^p\\ &={(-1)}^{|B|-|A|} \end{aligned} \]证毕。
子集反演公式
设 \(F,G:\mathcal P(X_n)\to\R\)，有反演公式：
\[G(K)=\sum\limits_{L\subseteq K}F(L)\iff F(K)=\sum\limits_{L\subseteq K}{(-1)}^{|K|-|L|}G(L) \]子集反演推论：容斥原理
最开始提到的容斥原理是可以用子集反演来推的。
设 \(A_i(i\in X_n)\)是有限集 \(S\) 的子集，对 \(K\subseteq X_n\)，定义 \(F(K)\) 为 \(S\) 中恰好在所有 \(A_i(i\notin K)\) 中的元素个数。特别地，\(F(X_n)=\left|\bigcap\overline{A_i}\right|\)。
记 \(G(K)=\sum\limits_{L\subseteq K}F(L)\)，即 \(S\) 中属于所有 \(A_i(i\notin K)\) 中的元素个数。特别地，\(G(X_n)=|S|\)。
因此：
\[G(K)= \begin{cases} |S|,&K=X_n\\ \left|\bigcap\limits_{i\notin K} A_i\right|,&K\ne X_n \end{cases} \]由子集反演公式：
\[G(K)=\sum\limits_{L\subseteq K}F(L)\iff F(K)=\sum\limits_{L\subseteq K}{(-1)}^{|K|-|L|}G(L) \]令 \(K=X_n\)，则有：
\[F(X_n)=\sum\limits_{L\subseteq X_n}{(-1)}^{n-|L|}G(L) \]也就是容斥原理。
子集反演推论：二项式反演
在子集反演公式中：
\[G(K)=\sum\limits_{L\subseteq K}F(L)\iff F(K)=\sum\limits_{L\subseteq K}{(-1)}^{|K|-|L|}G(L) \]设 \(F(K)=f(|K|),G(K)=g(|K|),n=|K|\)，即 \(F(K),G(K)\) 仅与 \(|K|\) 有关，即得到：
\[g(n)=\sum\limits_{i=0}^n\binom{n}{i}f(i)\iff f(n)=\sum\limits_{i=0}^n{(-1)}^{n-i}\binom{n}{i}g(i) \]上式进行变形可以得到二项式反演的另一种形式：
\[g(n)=\sum\limits_{i=0}^n{(-1)}^{i}\binom{n}{i}f(i)\iff f(n)=\sum\limits_{i=0}^n{(-1)}^{i}\binom{n}{i}g(i) \]子集反演、二项式反演应用
这个我还得学学，先咕着。