中等组合计数小结

(该小结为不定期更新，如有代码缺失和内容错误或不一致,以及其他可以改进的地方，请私信指出，在下定不胜感激)

前言

中等组合计数与初等组合计数大有不同，有人指出，初等组合计数看天赋，中等组合计数看套路，这句话很好地说明了我接下来，即将呈现给各位的知识的特点，也提示了应有的学习态度，我承认此处知识确实很高深，不好入门，本人也是在毫无外援，靠几篇博客所学,特此感谢peng-ym，我已体会到了单打独斗的痛苦与折磨了，特此作此小结，希望后人能少走弯路，直达思维迷宫的终点。

容斥原理

容斥原理

设有集合\(\{S_1,S_2,...,S_n\}\)，\(|S_i|\)表示集合大小，有：

\[|\bigcup_{i=1}^{n}S_i|=\sum_{i=1}^n|S_i|-\sum_{1\leq i<j\leq n}|S_i\bigcap S_j|+\sum_{1\leq i<j<k\leq n}|S_i\bigcap S_j\]

\[\bigcap S_k|-...+[-(-1)^n]|\bigcap_{i=1}^nS_i|\]

用途：直接做组合计数问题不好做，可以考虑容斥，

时间复杂度：\(O(2^n)\)

证明：

不妨提出交集集合数的概念，为几个集合交集，而集合重复次数，为该集合在进行大小计算时被累加的次数，于是可以列表

当前操作的意思是是否累加该个集合大小，于是

1.考虑原式的第1项

2.考虑原式的第2项

3.考虑原式的第3项

....

于是我们可以得到对于i个集合交集的重复次数，表达式应为\(C_i^1-C_i^2+C_i^3-...+[-(-1)^i]C_i^i=\sum_{j=1}^i[-(-1)^i]C_i^j\),而又有引理：

\[0=0^i=(1-1)^i=\sum_{j=0}^i(-1)^jC_i^j\]

\[\sum_{j=1}^i(-1)^jC_i^j=-1\Rightarrow\sum_{j=1}^i[-(-1)]^jC_i^j=1\]

故上式结果为1,于是我们可以说每个交集部分当且仅当重复一次，故得证。

多重集组合数

设\(\{n_1a_1,n_2a_2,...,n_ka_k\}\)表示有\(n_1\)个\(a_1\),\(n_2\)个\(a_2\)....的可重集合，从中取r个元素的方案数为

\[C_{k+r-1}^{k-1}-\sum_{i=1}^kC_{k+r-n_i-2}^{k-1}+\sum_{1\leq i<j\leq k}C_{k+r-n_i-n_j-3}^{k-1}-...+(-1)^kC_{k+r-(k+1)-\sum_{j=1}^kn_j}^{k-1}\]

证明：

所有方案数（不考虑元素的个数，即设其数量无限）不难得知是原式第一项，而当考虑其中一种元素必然不满足条件不难得知为原式第二项，但是如此导致方案数减多了，于是加回两种元素必然选多了，以此类推，不难得知为容斥。

练习

唯一分解定理

数学语言：\(n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}(gcd(p_1,p_2,...,p_m)==1)\)

文字语言：任何一个数有且仅能被分解成几个质因数之积。

用途：约数问题隐含条件

整除分块

形式：\(\sum_{i=a}^b[c/i]d\)

解法：\([c/i]=[c/[c/[c/i]]]\),所以\(i-[c/[c/i]]\)的值都相同，故一起处理。

时间复杂度：\(O(\sqrt n)\)

证明：\(c/i\in[1,\sqrt n]\),故得证。

狄利克雷卷积

定义:\((f*g)(n)=\sum_{d|n}f(d)g(n/d)\)（读做f卷g）

性质：

1. 交换律 \(f*g=g*f\)
2. 结合律\(f*g*h=f*(g*h)\)
3. 分配律\((f+g)*h=f*h+g*h\)

用途：

1. 函数证明
2. 推式

(完全)积性函数

概念

完全积性函数：

定义：\(f(pq)=f(p)f(q)\)

积性函数：

定义：\(f(pq)=f(p)f(q)(gcd(p,q)==1)\)

共性：

1. 积性函数卷积性函数仍为积性函数,不妨简称积积得积。

证明：
设\(h=f*g,gcd(p,q)==1\),有
\[h(p)h(q)=\sum_{x|p}f(x)g(p/x)*\sum_{y|q}f(y)g(q/y)\]

又有对于任意\(x,y,f(xy)=f(x)f(y),g(pq/xy)=g(p/x)g(q/y)\),故x，y对应pq的一个约数d的\(f(d),g(pq/d)\),而相反地\(f(d),g(pq/d)\)只能唯一分解成一对x,y,故得证。

特别地有\(f*I\)

1. 由唯一分解定理\(f(n)=f(p_1^{c_1})f(p_2^{c_2})...f(p_m^{c_m})\)

2. 设\(f\)为积性函数,\(f*\epsilon=f\)

线性筛积性函数

此处重点介绍Euler筛\(O(n)\)递推积性函数：

基本思路：

1. 证明该函数为积性函数。
2. 对于互质更新直接利用积性。
3. 解决\(f(n)=f(n/p)\times ?(p|n,p^2|n)\),通常对最小质因子进行考虑。

常见完全积性函数

恒等函数

符号：\(I\)

表达式：\(I(n)=1\)

性质：

1. \((f*I)(n)=\sum_{d|n}f(d)\)

单位函数

符号：\(id\)

表达式：\(id(n)=n\)

• 扩展：

\(id^2(n)=n^2\)也为完全积性函数，更一般地，\(id^k(n)=n^k\)也为积性函数。

元函数

符号：\(\epsilon\)

表达式：\(\epsilon(n)=(n==1)\)

性质：
\(f*\epsilon=f\)

常见积性函数

欧拉函数

符号：\(\varphi\)

表达式：\(\varphi(n)=n\prod_{i=1}^{m}\frac{p_i-1}{p_i}\)(\(p_i\)为n质因子)

性质：

1. 积性

2. \(\varphi(n)=\varphi(n/p)\times p(p\in prime,p|n,p^2|n)\)

证明：
\(\varphi(n)=n\prod_{i=1}^{m}\frac{p_i-1}{p_i}=\frac{n}{p}\prod_{i=1}^{m}\frac{p_i-1}{p_i}*p=\varphi(n/p)\times p\)

用途：线性递推

1. \(\varphi *I=id\ or\ \sum_{d|n}\varphi(d)=n\)

证明：
由积积得积易知\(\varphi*I\)也为积性函数，故不妨记\(f=\varphi*I\)，于是由唯一分解定理有\(f(n)=f(p_1^{c_1})f(p_2^{c_2})...f(p_m^{c_m})\),对于其中一项\(f(p_i^{c_i})=\varphi(1)+\varphi(p_i^1)+...+\varphi(p_i^{c_i})=1+p_i-1+p_i(p_i-1)\)
\(+...+p_i^{c_i-1}(p_i-1)=1+(p_i-1)(1+...+p_i^{c_i-1})=1+\)
\((p_i-1)\frac{p_i^{c_i}-1}{p_i-1}=1+p_i^{c_i-1}-1=p_i^{c_i}\),于是\(f(n)=p_1^{c_1}p_2^{c_2}...p_m^{c_m}=n\),所以得证。

用途：

1.隐含条件，式子证明

约数个数

符号：\(d\)

表达式：\(d(n)=\sum_{d|n}1=\sum_{i=1}^{n}(d|n)=(c_1+1)(c_2+1)...(c_m+1)\)

性质：

1. \(d(n)=\frac{d(n/p)f(n)}{f(n/p)}\)(f(n)表示其最小质因子的个数+1,由定义感性理解易证)

2. \((d*I)(n)=\sum_{d|n}d(d)=\prod_{i=1}^{m}\frac{(c_i+2)(c_i+1)}{2}\)

证明：

由积积得积设\(f(n)=\sum_{d|n}d(d)=f(p_1^{c_1})...f(p_m^{c_m})\),对于其中一项\(f(p_i^{c_i})=1+2+3+...+c_m+1=\frac{(c_m+2),(c_m+1)}{2}\)，合并易证。

1. \(\sum_{i=1}^nd(i)=\sum_{i=1}^n[\frac{n}{i}]\)

证明：

对于单个约数来看，每个约数\(i\)各\([\frac{n}{i}]\)个。

1. \(d=I*I\)

证明：

\((I*I)(n)=\sum_{d|n}1\),不难得知，每个约数都被统计了一次。故得证。

1. \(d(ij)=\sum_{x|i}\sum_{y|j}(gcd(x,y)==1)\)

证明：

考虑函数映射，对于\(ij\)中一个约数\(k\)而言，它由唯一分解定理有\(p^c\)这个质因子的次方，设\(i\)有\(p^a\),\(j\)有\(p^b\)，有以下的映射方式：

1. \(a\ge c\),从i中选择所需质因子。
2. \(a< c\),从j中选择\(p^{c-a}\)

以此对于\(ij\)的一个约数\(k\)我们能够生成唯一一对\(x,y\),而对于唯一一对\(x,y\)我们能唯一还原成一个\(k\),所以我们可以说它们是一一对应的，于是得证。

约数和

符号：\(\sigma\)

表达式：\(\sigma(n)=\sum_{d|n}d=\sum_{d=1}^n(d|n)d=\prod_{i=1}^m\sum_{j=0}^{c_i}p_i^{c_j}=\)

\((1+p_1+...+p_1^{c_1})(1+p_2+...+p_2^{c_2})...(1+p_m+...+p_m^{c_m})\)

性质：

1. \(\sigma(n)=\frac{\sigma(n/p)f(n)}{f(n/p)}=\prod_{i=0}^{c_1}p_i^{i}\),由定义感性理解易证)

2. \(\sum_{d|n}\sigma(d)=\prod_{i=1}^{m}\sum_{j=0}^{c_i}p_i^j(c_i-j+1)\)

证明：
由积积得积设\(f(n)=\sum_{d|n}\sigma(d)=\prod_{i=1}^mf(p_i^{c_i})\),对于其中一项\(f(p_i^{c_i})=1+1+p_i+1+p_i+p_i^2+...1+...+p_i^{c_i}=\)

\((c_i+1)+c_ip_i+...+p_i^{c_i}\)，合并即得证。

1. \(\sigma=I*id\)

证明：
\((I*id)(n)=\sum_{d|n}d\),此时不难得知每个约数的值都被累加了一次，故得证。

Mobius 函数

符号：\(\mu\)

表达式：

\(\mu(n)=0\)（有相同质因子）

\(\mu(n)=1\)（有偶数个不同质因子）

\(\mu(n)=-1\)（有奇数个不同质因子）

性质：

1. \(\sum_{d|n}\mu(d)=(n==1)\ or\ \mu*I=\epsilon\)

证明：

法一：数学归纳

1. 倒推（唯一分解定理+积积得积）

由积积得积设\(f(n)=\sum_{d|n}\mu(d)=\prod_{i=1}^{m}f(p_i^{c_i})\),对于其中一项有\(f(p_i^{c_i})=\mu(1)+\mu(p_i)+\mu(p_i^2)+...+\mu(p_i^{c_i})=0\),特别地，当n=1,不能进行质因数分解，此时结果为1，所以得证。

1. 顺推

假设\(\sum_{d|n}\mu(d)\)中该n以前所有数满足条件，考虑给n乘一个质数p，只是给原式多了一个取负的部分，而对于所有质数显然满足条件，特别的当n=1,不满足条件，等于1,故得证。

思路创造者：lsy

法二：容斥原理

不妨设n的质因数有c个，对于选取的d质因子次数为0,有\(C_c^0\),而次数为1,\(C_c^1\)...,则有

\[\sum_{d|n}\mu(d)=C_n^0-C_n^1+C_n^2-...+(-1)^nC_n^n\]

由上标公式易知该式只有当n=1时为1,其余情况为0,故得证。

1. \(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}or\ id*\mu=\varphi\)

证明：

法一（容斥）：

不难得知
\[\sum_{d|n}\frac{\mu(d)n}{d}=1-\sum_{i=1}^m\frac{n}{p_i}+\sum_{1\leq i<j \leq m}\frac{n}{p_ip_j}-\sum_{1\leq i<j <k\leq m}\frac{n}{p_ip_jp_k}+\]

\[...+(-1)^m\frac{n}{\prod_{i=1}^mp_i}\]

由容斥原理不难得知\(\sum_{d|n}\frac{\mu(d)n}{d}=\varphi(n)\),即\(\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\),故得证。

法二（狄利克雷卷积）：

注意到\((\mu*id)(n)=\sum_{d|n}\mu(d)id(n/d)=\sum_{d|n}\frac{\mu(d)n}{d}\),且有
\[\varphi*I=id\]
\[\varphi*I*\mu=id*\mu\]
\[\varphi*\epsilon=id*\mu\]
\[\varphi=id*\mu\]
即
\[\sum_{d|n}\frac{\mu(d)n}{d}=\varphi(n)\]
所以
\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\]

Mobius反演

约数型

\[F(n)=\sum_{d|n}f(d)\Rightarrow f(n)=\sum_{d|n}\mu(d)F(n/d)=\]
\[\sum_{d|n}\mu(n/d)F(d)\]

证明：

1. 容斥：

把\(f(d)\)抽象成d这个约数的性质，\(F(n)\)即n的所有约数的性质之和，故要求\(f(n)\),我们先把\(F(n)\)减去\(F(d)\),d正好比n少一个质因子，而系数正好为\(\mu(n/d)\),但是这样减多了，于是加回\(F(d)\),此处d正好比n少两个不同质因子，系数也正好为\(\mu(n/d)\)，...，于是得证。

1. 代数：

\[\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i)=\sum_{i=1}^{n}f(i)\sum_{i|\frac{n}{d},d|n}\mu(d)\]

\[=\sum_{i=1}^{n}f(i)\sum_{d|\frac{n}{i}}\mu(d)=\sum_{i=1}^{n}f(i)(\frac{n}{i}==1)=f(n)\]

1. 狄利克雷卷积：

注意到\(F=f*I,\mu*i=\epsilon\),所以

\[F=f*I\]

\[F*\mu=f*I*\mu\]

\[F*\mu=f*\epsilon\]

\[F*\mu=f\]

即

\[f(n)=\sum_{d|n}\mu(d)F(n/d)\]

倍数型：

\[F(n)=\sum_{n|d}f(d)\Rightarrow f(n)=\sum_{n|d}\mu(d/n)F(d)=\]
\[\sum_{d|n}\mu(d)F(d/n)\]

证明：

1. 代数：

\[\sum_{n|d}\mu(d/n)F(d)=\sum_{n|d}\mu(d/n)\sum_{d|i}f(i)=\]
\[\sum_{n|i}f(i)\sum_{n|d,d|i}\mu(d/n)=\sum_{n|i}f(i)\sum_{d|\frac{n}{i}}\mu(d)=\]

\[\sum_{n|i}f(i)(\frac{n}{i}==1)=f(n)\]

1. 狄利克雷卷积：

考虑已经证过约数型的式子，而狄利克雷卷积不适合倍数型的式子，考虑分数倒置，设\(F'(n)=F(\frac{1}{n}),f'(n)=f(\frac{1}{n}),F(n)=\sum_{d|n}f(d)\),故有：

\[F'(n)=F(\frac{1}{n})=\sum_{d|\frac{1}{n}}f(d)=\sum_{n|\frac{1}{d}}f(d)=\sum_{n|\frac{1}{d}}f'(\frac{1}{d})=\sum_{n|d}f'(d)\]

而

\[f(n)=\sum_{d|n}F(d)\mu(n/d)\]
\[f(\frac{1}{n})=\sum_{n|\frac{1}{d}}F(d)\mu(1/nd)\]
\[f(\frac{1}{n})=\sum_{n|d}F(\frac{1}{d})\mu(d/n)\]
\[f'(n)=\sum_{n|d}F'(d)\mu(d/n)\]

故得证

练习

杜教筛

明确作用：线性筛的优化

基本表达式：

设\(f,g,h\)均为积性函数并满足\(h=f*g\)，\(f\)为所求，并设\(s(n)=\sum_{i=1}^nf(i)\),有

\[g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)s(n/d)\]

证明：

\[\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}f(i/d)g(d)=\sum_{d=1}^{n}\sum_{i=1}^n(d|i)f(i/d)g(d)=\]
\[\sum_{d=1}^{n}g(d)\sum_{i=1}^{[n/d]}f(i)=g(1)\sum_{i=1}^nf(i)+\sum_{d=2}^{n}g(d)\sum_{i=1}^{[n/d]}f(i)=\]
\[g(1)s(n)+\sum_{d=2}^{n}g(d)\sum_{i=1}s(n/d)\]
\[g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)s(n/d)\]

故得证

实例：

1. \(s(n)=\sum_{i=1}^n\mu(i)\)

解：

注意到\(\mu*I=\epsilon\),所以所需杜教筛式子为\(I(1)s(n)=\sum_{i=1}^n\epsilon(i)-\sum_{d=2}^nI(d)s(n/d)\),化简即\(s(n)=1-\sum_{d=2}^ns(n/d)\)，故问题解决。

1. \(s(n)=\sum_{i=1}^n\varphi(i)\)

解：

注意到\(\varphi*I=id\),所以杜教筛式子为\(I(1)s(n)=\sum_{i=1}^nid(i)-\sum_{d=2}^nI(d)s(n/d)\),即\(s(n)=\frac{(1+n)n}{2}-\sum_{d=2}^ns(n/d)\),故问题得解。

1. \(s(n)=\sum_{i=1}^ni\varphi(i)\)

解：

此题无直接性质，故考虑待定函数，设\(h=f*g,f(n)=n\varphi(n)\),有\(h(n)=\sum_{d|n}d\varphi(d)g(n/d)\),而要简化式子，自然想到\(\frac{n}{d}d=n\),于是猜\(g=id\),故\(h(n)=n\sum_{d|n}\varphi(n)=n^2\),所以所求杜教筛式子为\(id(1)s(n)=\sum_{i=1}^ng(i)-\sum_{d=2}^nid(d)s(n/d)\),化简即\(s(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{d=2}^nd\times s(n/d)\),故问题解决。

练习

1. 定义一个函数\(f(n)\),把n进行质因数分解，得到\(n=\prod_{i=1}^mp_i^{c_i}\),函数值即对于每一个\(p_i^{c_i}\),如果次数等于1，则累乘-2,次数等于2,则累乘1,否则累乘0的值,如\(f(50)=1\times(-2)=-2\),现在有些询问，询问组数为t\((t\leq 100)\),每次询问\(\sum_{i=1}^nf(n)\)的值\((n\leq 10^{10})\)。

套路总结

约数结论小结

1. \(gcd(a,b)\leq|a-b|(a!=b)\)
2. 积和互质结论：\(gcd(a,b)=1\Rightarrow gcd(a+b,ab)=1\)
3. \(gcd(a,b,c)=gcd(gcd(a,b),c)\)
4. \(gcd(ak,bk,c)=gcd(k\times gcd(a,b),c)\)

约数计数问题

三种角度:

\[num\]
\[\swarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \nwarrow\]
\[divisor\ \ \rightarrow \ \ \ prime\ factor\]

两大思路：

Mobius反演\(\Longleftrightarrow\)容斥原理

等式变换:

对应相等\(\Longleftrightarrow\)约数拆分
（反证法，分数反证，因式分解）

杜教筛

1. 看是否有现成积性函数
2. 寻找积性函数性质
3. 待定函数法确定积性函数

式子证明套路：

数列

1. 等差
2. 扩大做差
3. 几何意义

狄利克雷卷积：

1. 寻找积性函数
2. 寻找积性性质
3. 列出积性等式
4. 试图抵消并配出所需

（对于倍数型式子可采取分数倒置的方法）

映射：

1. 寻找映射对象
2. 寻找映射方式
3. 证明一一对应

适用范围：函数的证明

质因数分解

注意1不能质因数分解的情况

积积得积

1. 试图证明积性（利用积积得积，或暴力证明）。
2. 数学归纳唯一分解定理分解，对单个质因子次方考虑。

容斥

1. 明确被容斥对象
2. 寻找容斥对象（注意前后正反都可以）
3. 递推寻找加加减减关系

数学归纳

1. 明确状态
2. 转移方程（顺退，倒推）
3. 边界

中等组合计数与数据结构

1. 不离线白不离线。
2. 要求某项小于某数，保留该项，排序选择。
3. 什么变，维护什么。

式子变换套路

容斥

1. 尽可能把式子除成质数或互质形式

Mobius反演

1. \(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)==k\),Monius反演常见标志。
2. 半个Mobius反演。
3. 默认\(a<b\)简化问题。
4. 单个gcd枚举提前。
5. \(\sum_{d|gcd(i,j)}\mu(d)=(gcd(i,j)==1)\)可一定程度上代替Mobius反演。
6. 整除分块前放。
7. \(\sum_{k|d}\sum...\sum(a==d)=\sum...\sum(k|a)\)

\(\sum\)变换

可维护

1. \(\sum_{n|d}f(d/n)\)
2. \(\sum_{d|n}\mu(d)f(n/d)\)。

变式

1. \([[a/b]/c]=[\frac{a}{bc}]\)。
2. \(\sum_{d|i}\)枚举提前，或换元消判。
3. \(\sum_{d|n}f(d)g(n/d)=\sum_{d|n}f(n/d)g(d)\)两种形式虽等价，但推式难度有差别。
4. 缩小枚举\(i=i'k,\sum_{i=a}^b(k|i)i=\sum_{i=[\frac{a-1}{k}]+1}^{\frac{b}{k}}ik\)
5. 放大枚举\(i'=ik,\sum_{i=a}^bik=\sum_{i=ak,k|i}^{bk}i\)
6. \(\sum_{i=1}^a\sum_{j=1}^b[a/i][b/j]\)为约数函数前缀和。
7. \(\sum_{i=1}^a\sum_{j=1}^bij\)为两次等差。

\(\prod\)变换

其他

1. 能代就代。

尾声

恭喜您，您已经达到了我的Mobius反演的水平，但是我的水平也不过沧海一粟，远远不够您的继续深造，但愿我微薄的一点总结，能让你走的更远

中等组合计数小结

原文：https://www.cnblogs.com/a1b3c7d9/p/10781608.html