总结

Min_25筛

Min_25 筛 引入 $O(n^{3/4}/\log n)$ 求一些积性函数的前缀和 质数贡献 我们先求 $$ G(m)=\sum_{i=2}^{m}[i \in prime]f(i) $$ 假设有一个函数 完全积性函数 $f'$ 在质数处与 $f$ 取值相同。我们可以改为求 $$...

范德蒙恒等式

范德蒙恒等式 $$ \sum_{i=0}^kC_n^iC_m^{k-i}=C_{n+m}^k $$ 证明: 组合意义 右边式子的组合意义为从 $n+m$ 个物品中取出总共 $k$ 个的方案数。左边式子和右边式子组合意义相同。 生成函数 $$...

FWT

引入 求 $$ \sum_{i=1}^n c_i=\sum_{j\oplus k=i} a_jb_k (n\le 1e5) $$ 其中 $\oplus$ 表示一种二元位运算 与、或 正变换 对于 按位或 运算,我们若有 $i\ \text{or}\ k=k$ 和 $j\ \text{or}\ k=k...

莫比乌斯反演

莫比乌斯函数 $$ \begin{equation} \mu(n)=\left\{ \begin{array}{lr} 1 \qquad\qquad\qquad n=1\\ (-1)^k\qquad\qquad n为k个不同素数的乘积 \\ 0\qquad\qquad\qquad 其它 \end{array} \right. \end{equatio...

素数无穷个的证明

方法1 设: $n \ge 0$, $F_n=2^{2^n}+1(Fermat\ Number)$ ,设 $n\neq m$ ,若 $d > 1,d \mid F_n$ 则 $d$ 不整除 $F_m$ 。 证明: 不妨设 $m>n$,则有 $$ F_n \mid F_m -2 = 2^{2^m}-1=(2^{2^{n}...

NTT

在 $\text{FFT}$ 中,我们使用复数的单位根进行 $DFT$,这样会产生浮点数误差。对于只有整数参与的多项式运算,我们需要找到正好的方法。 引入 考虑 $\text{FFT}$ 的时候我们为什么选择使用复数单位根。 $...

欧拉函数

在数论中,对 正整数 $n$, 欧拉函数 $\phi(n)$ 是 小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。 求欧拉函数值 首先我们考虑素数的欧拉函数值,素数肯定与小于本身的正整数互质,所以 $\phi(p)=p-1$ ...

FFT

点值表示法 $n$个二维平面上的点$(x_1,y_1)…(x_n,y_n)$,确定了唯一一个过这些点的 $n-1$次多项式。 证明:设 $n-1$ 次多项式 $f(x),g(x)$ 都经过这 $n$ 个点,设 $n-1$ 次多项式 $y(x)=f(x)-g(x)$,那么$y(...

CDQ 分治

逆序对-梦开始的地方 题目:给定序列$s,|s|\leq 1e5$,求序列中逆序对的数量 一种解法当然是离散化以后用树状数组求啦. 另外一种方法就是 归并排序,采用分治的思想,一个区间中全部的逆序对数等于左区...

最大权闭合图

定义 设一个图$G=(V,E)$的闭合图$G'=(V',E')$,满足对$\forall v \in V'$引出的$\forall \left<s,u\right>\in E$有$u\in V'$。则该图为一个闭合图。一个图中点权和最大的闭合子图称为该图的最大闭合图...