星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

数论套路整理

posted on 2018-03-25 19:36:19 | under Diary |

P.S.

https://blog.csdn.net/wu_tongtong/article/details/78936308 有一个博客总结的内容似乎也不错 $\cdots\cdots$

数论函数相关:

化简gcd:

$$\sum_{i=1}^n\sum_{j=1}^{n}(i,j)$$ $$=\sum_{p=1}^np\sum_{i=1}^n\sum_{j=1}^{n}[(i,j)==p]$$ $$=\sum_{p=1}^np\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[(i,j)==1]$$ $$=\sum_{p=1}^np\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{d\vert (i,j)}\mu(d)$$ $$=\sum_{p=1}^np\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{pd}\rfloor}1$$ $$=\sum_{p=1}^np\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)(\lfloor\frac{n}{pd}\rfloor)^2$$ 设 $T=pd$ 。 $$ans=\sum_{T=1}^{n}(\lfloor\frac{n}{T}\rfloor)^2\sum_{p\vert T}p\mu(\lfloor\frac{n}{p}\rfloor)$$ $$=\sum_{T=1}^{n}(\lfloor\frac{n}{T}\rfloor)^2\varphi(T)$$
上面那内容是自己高一的时候瞎写的,现在写一个比较靠谱的理解。
首先第一步很正常,也很显然。
然后第二步我们更换了枚举项,这里枚举的 $i,j$ 指的是原来 $i,j$ 默认乘了个 $p$ 之后剩下的,因此它们要满足互质,这样 $gcd$ 才是 $p$ 。
第三步用的是莫比乌斯函数的性质。
第四步我们枚举 $\mu(d)$ ,后面也更换了枚举项,表示枚举原来 $i,j$ 默认乘了个 $d$ 剩下的,它们没有限制,都可以取。第五步就是化简了一下。
第六步更换了枚举项,枚举了 $pd$ ,然后把它提前。考虑现在的 $pd$ ,一定是 $T$ 的因子,而且相乘 $=T$ ,因此这么枚举。
第七步就是 $id\ast\mu=\varphi$ 。
或者 $$ans=\sum_{i=1}^n\sum_{j=1}^{n}\sum_{d\vert(i,j)}\varphi(d)$$ $$=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}1$$ $$=\sum_{d=1}^n\varphi(d)(\lfloor\frac{n}{d}\rfloor)^2$$ 第一种推法的普适性更强,但在(i,j)次数为1的情况下,第二种推法能大大简化过程。毕竟上面最终会变成下面。

线性筛:

在 $Vazuku,40.$

杜教筛:

设 $f\ast g=h$ ,若 $G,H$ 易求,则 $F$ 易求。
$$g(1)F(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^ng(i)F(\lfloor\frac{n}{i}\rfloor)$$ 对于这个式子,它化简后的形式应该是 $count1=count2-\sum_{i=2}^ncount3F(\lfloor\frac{n}{i}\rfloor)$ 。我们可以直接线性筛 $O(n^\frac{2}{3})$ 预处理,之后的部分递归就好了。
杜教筛没啥好讲的因为不会证明,就是注意一下它求的是 $F$ ,所以要求啥你得把它变成 $F$ ,另外就是如果函数里带 $\mu$ 可以让 $g=1$ 卷一下 $\mu$ 就变成 $\epsilon$ 了。

Min_25筛:

在学了qwq。学了,在 $Miloring,49.$

欧拉函数:

$$\varphi(n)=n-n\sum p_i+n\sum p_ip_j-\cdots$$ $$=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n})$$ $$n=\sum_{d\vert n}\varphi(d)$$ 即 $$\varphi\ast 1=id$$
$$id\ast\mu=\varphi$$ 实质是欧拉函数与莫比乌斯函数关系式 $\frac{\varphi(n)}{n}=\sum_{d\vert n}\frac{\mu(d)}{d}$ 的推导结果。但或者你也可以利用这个式子证明关系式。
直接用狄利克雷卷积证明: $$id\ast\mu$$ $$=1\ast\varphi\ast\mu$$ $$=\varphi\ast e$$ $$=\varphi$$

线性求逆元:

设 $p=kx+r$ $$kx+r\equiv 0\pmod p$$ 两边同乘 $\frac{1}{xr}$ $$\frac{k}{r}+\frac{1}{x}\equiv 0\pmod p$$ $$\frac{1}{x}\equiv -\frac{k}{r}$$ $$\frac{1}{x}\equiv -\frac{\lfloor\frac{p}{x}\rfloor}{p\%i}\pmod p$$
实际上,直接预处理阶乘及其逆元就可以求了。所以我们要这玩意儿干啥?或许是小模数吧

斯特林数:

第一类斯特林数:

$$S_1(n,k)=S_1(n-1,k-1)+(n-1)S_1(n-1,k)$$ 第一类斯特林数的生成函数是这样的: $$\sum_{i=0}^{n}S_1(n,i)x^i=\prod_{i=0}^{n-1}(x+i)$$ 简单理解一下就是,出一个新环代表 $x$ ,放进之前的数的旁边代表 $i$ (因为 $i$ 从0枚举所以是对的)
有一个带符号斯特林数是带个 $(-1)^{n-i}$ ,生成函数变成了 $$\prod_{i=0}^{n-1}(x-i)$$ 第一类斯特林数有一个类似多项式算法的倍增FFT求法,由神威本人发现并证明:
我们设 $F_{n}(x)=\sum_{i=0}^{n}S_1(n,i)x^i=\prod_{i=0}^{n-1}(x+i)$ ,那么 $F_{2n}(x)=F_n(x)F_n(x+n)$ 。
$$\begin{aligned}F_n(x+n)=&\sum_{i=0}^{n}S_1(n,i)(x+n)^i\\=&\sum_{i=0}^{n}S_1(n,i)\sum_{j=0}^i\binom{i}{j}x^jn^{i-j}\\=&\sum_{j=0}^nx^j\sum_{i=j}^{n}S_1(n,i)\binom{i}{j}n^{i-j}\\=&\sum_{j=0}^nx^j\sum_{i=j}^{n}\frac{S_1(n,i)i!n^{i-j}}{j!(i-j)!}\\=&\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=j}^{n}\frac{S_1(n,i)i!n^{i-j}}{(i-j)!}\\=&\sum_{j=0}^n\frac{x^j}{j!}\sum_{(n-i)=0}^{n-j}\frac{S_1(n,i)i!n^{i-j}}{(i-j)!}\\=&\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=0}^{n-j}\frac{S_1(n,n-i)(n-i)!n^{n-j-i}}{(n-j-i)!}\\=&\sum_{j=0}^n\frac{x^j}{j!}\sum_{i=0}^{n-j}S_1(n,n-i)(n-i)!\frac{n^{n-j-i}}{(n-j-i)!}\\\end{aligned}$$
将前面两个序列翻转,就变成了卷积形式。

第二类斯特林数:

$$S_2(n,k)=S_2(n-1,k-1)+kS_2(n-1,k)$$ $$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n$$ $$=\sum_{k=0}^m(-1)^k\frac{1}{(m-k)!k!}(m-k)^n$$ $$=\sum_{k=0}^m\frac{(-1)^k}{k!}\times \frac{(m-k)^n}{(m-k)!}$$ 设 $a_i=\frac{(-1)^i}{i!}$ , $b_i=\frac{i^n}{i!}$ 。
那么原式 $=\sum_{k=0}^ma_kb_{m-k}$ ,是一个卷积形式,直接用 $NTT/FFT$ 求解就可以了。 $$n^k=\sum_{i=0}^kS(k,i)\times\binom{n}{i}\times i!$$ $$=n!\sum_{i=0}^kS(k,i)\times\frac{1}{(n-i)!}$$ 这个式子的特点是,你可以把n带入组合数中,而不像二项式定理一样与n(a+b)无关。

组合数:

二项式定理:

$$\sum_{i=0}^k\binom{k}{i}a^{k-i}b^i=(a+b)^k$$ 某些时候可以很方便地化成卷积形式。

组合数的性质:

$$\binom{n}{i}\binom{n-i}{j}=\binom{n}{j}\binom{n-j}{i}$$ $$\sum_{i=0}^n\binom{m+i}{i}=\binom{n+m+1}{n}$$ 证明是很显然的。 $\binom{m}{0}=\binom{m+1}{0}$ ,转换一下之后直接利用组合数递推公式证明就可以了。

隔板法相关:

$$\binom{n-1+m}{n-1}$$
表示 $n-1+m$ 个位置放置 $n-1$ 个板子,把 $m$ 个数分成 $n$ 个部分的方案数。它有很多组合意义,是非常方便的一个手段。
譬如,在 $n$ 个物品中选 $m$ 个,可以重复选的方案数。其组合意义是,这 $n$ 段总和为 $m$ ,每一段的长度就是选择的物品数量。

自然数幂和:

伯努利数:

$$B=\{1,-\frac12,\frac16,0,-\frac1{30},0,\frac1{42},\cdots\}$$
有个结论就是 $$B(x)=\frac x{e^x-1}=\frac x{\sum_{i=1}^\infty \frac{x^i}{i!}}=\frac 1{\sum_{i=1}^\infty \frac{x^{i-1}}{i!}}=\frac 1{\sum_{i=0}^\infty \frac{x^{i}}{(i+1)!}}$$ ,然后就可以多项式求逆了。

反演:

二项式反演:

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

双重形式的莫比乌斯反演:

若 $$f(n)=\sum_{d\vert n}g(d)$$ 则 $$ g(n)=\sum_{d\vert n}\mu(d)f(\frac{n}{d})$$ 或 $$g(n)=\sum_{d\vert n}\mu(\frac{n}{d})f(d)$$ 若 $$f(n)=\sum_{n\vert d}g(d)$$ 则 $$g(n)=\sum_{n\vert d}\mu(d)f(\frac{d}{n})$$ 或 $$g(n)=\sum_{n\vert d}\mu(\frac{d}{n})f(d)$$ 可以直接用狄利克雷卷积、 $\mu\ast1=\epsilon$ 证。

斯特林反演:

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

最值反演:

$$(E)\ max\{T\}=\sum_{S\subseteq T}(-1)^{\vert S\vert-1}min\{S\}$$

子集反演:

$$f(S)=\sum_{T\subseteq S}g(T)$$ 则 $$g(S)=\sum_{T\subseteq S}(-1)^{\vert S\vert-\vert T\vert}f(T)$$ 子集反演也可以有第二种形式,把 $-1$ 的上标改为 $T-S$ 就可以了。

子集卷积:

看不懂。 还是看不懂。
看懂了,感谢 $fakesky$ 教授的集合幂级数这一套。

形式幂级数与集合幂级数:

详见计数总结 $slide$ 。

群论:

一个长度为 $n$ 的环,每次循环移 $x$ 位,它的置换循环节长度是 $\frac{n}{(x,n)}$ ,循环节个数为 $(x,n)$ 。证明可以看这个

以下没有用:

CF932E Team Work

求 $$\sum_{i=1}^{n}C(n,i)i^{k}$$
$$n<=1e9,k<=2e3.$$ 一道好题,利用 $i^{k}$ 转化为斯特林数的方式 $\Theta(k)$ 递推求解。预处理斯特林数 $\Theta(k^2)/\Theta(k\log k)(FFT/NTT)$ 。

Hihocoder #1456 Rikka with Lattice

神仙题啊......(待补充