目录
前言
容斥原理
容斥原理
多重集组合数
唯一分解定理
整除分块
狄利克雷卷积
(完全)积性函数
概念
共性:
线性筛积性函数
常见完全积性函数
常见积性函数
Mobius 反演
约数型
倍数型:
杜教筛
基本表达式:
实例:
练习
套路总结
约数结论小结
约数计数问题
杜教筛
式子证明套路:
中等组合计数与数据结构
式子变换套路
尾声
(该小结为不定期更新, 如有代码缺失和内容错误或不一致, 以及其他可以改进的地方, 请私信指出, 在下定不胜感激)
前言
中等组合计数与初等组合计数大有不同, 有人指出, 初等组合计数看天赋, 中等组合计数看套路, 这句话很好地说明了我接下来, 即将呈现给各位的知识的特点, 也提示了应有的学习态度, 我承认此处知识确实很高深, 不好入门, 本人也是在毫无外援, 靠几篇博客所学, 特此感谢 https://www.cnblogs.com/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 | 2 | 3 | ... | i | ... | n |
---|---|---|---|---|---|---|---|
符号表示 | \(S_i\) | \(S_i\bigcap S_j\) | \(S_i\bigcap S_j \bigcap S_k\) | ... | \(\bigcap_{j=1}^iS_j\) | ... | \(\bigcap_{j=1}^nS_j\) |
集合重复次数 | |||||||
当前操作 |
当前操作的意思是是否累加该个集合大小, 于是
1. 考虑原式的第 1 项
交集集合数 | 1 | 2 | 3 | ... | i | ... | n |
---|---|---|---|---|---|---|---|
符号表示 | \(S_i\) | \(S_i\bigcap S_j\) | \(S_i\bigcap S_j \bigcap S_k\) | ... | \(\bigcap_{j=1}^iS_j\) | ... | \(\bigcap_{j=1}^nS_j\) |
集合重复次数 | \(C_1^1\) | \(C_2^1\) | \(C_3^1\) | ... | \(C_i^1\) | ... | \(C_n^1\) |
当前操作 | + |
2. 考虑原式的第 2 项
交集集合数 | 1 | 2 | 3 | ... | i | ... | n |
---|---|---|---|---|---|---|---|
符号表示 | \(S_i\) | \(S_i\bigcap S_j\) | \(S_i\bigcap S_j \bigcap S_k\) | ... | \(\bigcap_{j=1}^iS_j\) | ... | \(\bigcap_{j=1}^nS_j\) |
集合重复次数 | \(C_1^1\) | \(C_2^1-C_2^2\) | \(C_3^1-C_3^2\) | ... | \(C_i^1-C_i^2\) | ... | \(C_n^1-C_n^2\) |
当前操作 | \(+\) | \(-\) |
3. 考虑原式的第 3 项
交集集合数 | 1 | 2 | 3 | ... | i | ... | n |
---|---|---|---|---|---|---|---|
符号表示 | \(S_i\) | \(S_i\bigcap S_j\) | \(S_i\bigcap S_j \bigcap S_k\) | ... | \(\bigcap_{j=1}^iS_j\) | ... | \(\bigcap_{j=1}^nS_j\) |
集合重复次数 | \(C_1^1\) | \(C_2^1-C_2^2\) | \(C_3^1-C_3^2+C_3^3\) | ... | \(C_i^1-C_i^2+C_i^3\) | ... | \(C_n^1-C_n^2+C_n^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}\]
证明:
所有方案数 (不考虑元素的个数, 即设其数量无限) 不难得知是原式第一项, 而当考虑其中一种元素必然不满足条件不难得知为原式第二项, 但是如此导致方案数减多了, 于是加回两种元素必然选多了, 以此类推, 不难得知为容斥.
练习 https://www.luogu.org/problemnew/show/CF451E
唯一分解定理
数学语言:\(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)
性质:
交换律 \(f*g=g*f\)
结合律 \(f*g*h=f*(g*h)\)
分配律 \((f+g)*h=f*h+g*h\)
用途:
函数证明
推式
(完全)积性函数
概念
完全积性函数:
定义:\(f(pq)=f(p)f(q)\)
积性函数:
定义:\(f(pq)=f(p)f(q)(gcd(p,q)==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\)
由唯一分解定理 \(f(n)=f(p_1^{c_1})f(p_2^{c_2})...f(p_m^{c_m})\)
设 \(f\)为积性函数,\(f*\epsilon=f\)
线性筛积性函数
此处重点介绍 Euler 筛 \(O(n)\)递推积性函数:
基本思路:
证明该函数为积性函数.
对于互质更新直接利用积性.
解决 \(f(n)=f(n/p)\times ?(p|n,p^2|n)\), 通常对最小质因子进行考虑.
常见完全积性函数
恒等函数
符号:\(I\)
表达式:\(I(n)=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 质因子)
性质:
积性
\(\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\)
用途: 线性递推
\(\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)\)
性质:
\(d(n)=\frac{d(n/p)f(n)}{f(n/p)}\)(f(n)表示其最小质因子的个数 + 1, 由定义感性理解易证)
\((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}\), 合并易证.
\(\sum_{i=1}^nd(i)=\sum_{i=1}^n[\frac{n}{i}]\)
证明:
对于单个约数来看, 每个约数 \(i\)各 \([\frac{n}{i}]\)个.
\(d=I*I\)
证明:
\((I*I)(n)=\sum_{d|n}1\), 不难得知, 每个约数都被统计了一次. 故得证.
\(d(ij)=\sum_{x|i}\sum_{y|j}(gcd(x,y)==1)\)
证明:
考虑函数映射, 对于 \(ij\)中一个约数 \(k\)而言, 它由唯一分解定理有 \(p^c\)这个质因子的次方, 设 \(i\)有 \(p^a\),\(j\)有 \(p^b\), 有以下的映射方式:
\(a\ge c\), 从 i 中选择所需质因子.
\(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})\)
性质:
\(\sigma(n)=\frac{\sigma(n/p)f(n)}{f(n/p)}=\prod_{i=0}^{c_1}p_i^{i}\), 由定义感性理解易证)
\(\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}\), 合并即得证.
\(\sigma=I*id\)
证明:
\((I*id)(n)=\sum_{d|n}d\), 此时不难得知每个约数的值都被累加了一次, 故得证.
Mobius 函数
符号:\(\mu\)
表达式:
- \(\mu(n)=0\)(有相同质因子)
- \(\mu(n)=1\)(有偶数个不同质因子)
- \(\mu(n)=-1\)(有奇数个不同质因子)
性质:
\(\sum_{d|n}\mu(d)=(n==1)\ or\ \mu*I=\epsilon\)
证明:
法一: 数学归纳
倒推(唯一分解定理 + 积积得积)
由积积得积设 \(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, 所以得证.
顺推
假设 \(\sum_{d|n}\mu(d)\)中该 n 以前所有数满足条件, 考虑给 n 乘一个质数 p, 只是给原式多了一个取负的部分, 而对于所有质数显然满足条件, 特别的当 n=1, 不满足条件, 等于 1, 故得证.
思路创造者: lsy https://www.luogu.org/space/show?uid=57001
法二: 容斥原理
不妨设 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, 故得证.
\(\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)\]
证明:
容斥:
把 \(f(d)\)抽象成 d 这个约数的性质,\(F(n)\)即 n 的所有约数的性质之和, 故要求 \(f(n)\), 我们先把 \(F(n)\)减去 \(F(d)\),d 正好比 n 少一个质因子, 而系数正好为 \(\mu(n/d)\), 但是这样减多了, 于是加回 \(F(d)\), 此处 d 正好比 n 少两个不同质因子, 系数也正好为 \(\mu(n/d)\),..., 于是得证.
代数:
- \[\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)\]
狄利克雷卷积:
注意到 \(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)\]
证明:
代数:
- \[\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)\]
狄利克雷卷积:
考虑已经证过约数型的式子, 而狄利克雷卷积不适合倍数型的式子, 考虑分数倒置, 设 \(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)\]
故得证
练习 https://www.luogu.org/problemnew/show/P4450
杜教筛
明确作用: 线性筛的优化
基本表达式:
设 \(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)\]
故得证
实例:
\(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)\), 故问题解决.
\(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)\), 故问题得解.
\(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)\), 故问题解决.
练习
定义一个函数 \(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})\).
套路总结
约数结论小结
\(gcd(a,b)\leq|a-b|(a!=b)\)
积和互质结论:\(gcd(a,b)=1\Rightarrow gcd(a+b,ab)=1\)
- \(gcd(a,b,c)=gcd(gcd(a,b),c)\)
- \(gcd(ak,bk,c)=gcd(k\times gcd(a,b),c)\)
约数计数问题
三种角度:
- \[num\]
- \[\swarrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \nwarrow\]
- \[divisor\ \ \rightarrow \ \ \ prime\ factor\]
两大思路:
Mobius 反演 \(\Longleftrightarrow\)容斥原理
等式变换:
对应相等 \(\Longleftrightarrow\)约数拆分
(反证法, 分数反证, 因式分解)
杜教筛
看是否有现成积性函数
寻找积性函数性质
待定函数法确定积性函数
式子证明套路:
数列
等差
扩大做差
几何意义
狄利克雷卷积:
寻找积性函数
寻找积性性质
列出积性等式
试图抵消并配出所需
(对于倍数型式子可采取分数倒置的方法)
映射:
寻找映射对象
寻找映射方式
证明一一对应
适用范围: 函数的证明
质因数分解
注意 1 不能质因数分解的情况
积积得积
试图证明积性(利用积积得积, 或暴力证明).
数学归纳唯一分解定理分解, 对单个质因子次方考虑.
容斥
明确被容斥对象
寻找容斥对象(注意前后正反都可以)
递推寻找加加减减关系
数学归纳
明确状态
转移方程(顺退, 倒推)
边界
中等组合计数与数据结构
不离线白不离线.
要求某项小于某数, 保留该项, 排序选择.
什么变, 维护什么.
式子变换套路
容斥
尽可能把式子除成质数或互质形式
Mobius 反演
\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)==k\),Monius 反演常见标志.
半个 Mobius 反演.
默认 \(a<b\)简化问题.
单个 gcd 枚举提前.
\(\sum_{d|gcd(i,j)}\mu(d)=(gcd(i,j)==1)\)可一定程度上代替 Mobius 反演.
整除分块前放.
\(\sum_{k|d}\sum...\sum(a==d)=\sum...\sum(k|a)\)
\(\sum\)变换
可维护
- \(\sum_{
- n|d
- }f(d/n)\)
- \(\sum_{
- d|n
- }\mu(d)f(n/d)\).
变式
\([[a/b]/c]=[\frac{a}{bc}]\).
\(\sum_{d|i}\)枚举提前, 或换元消判.
\(\sum_{d|n}f(d)g(n/d)=\sum_{d|n}f(n/d)g(d)\)两种形式虽等价, 但推式难度有差别.
缩小枚举 \(i=i'k,\sum_{i=a}^b(k|i)i=\sum_{i=[\frac{a-1}{k}]+1}^{\frac{b}{k}}ik\)
放大枚举 \(i'=ik,\sum_{i=a}^bik=\sum_{i=ak,k|i}^{bk}i\)
\(\sum_{i=1}^a\sum_{j=1}^b[a/i][b/j]\)为约数函数前缀和.
\(\sum_{i=1}^a\sum_{j=1}^bij\)为两次等差.
\(\prod\)变换
其他
能代就代.
尾声
恭喜您, 您已经达到了我的 Mobius 反演的水平, 但是我的水平也不过沧海一粟, 远远不够您的继续深造, 但愿我微薄的一点总结, 能让你走的更远
来源: http://www.bubuko.com/infodetail-3038787.html