常用知识点及易错点总结

由于博主是个沙雕所以需要在这里记录一些比较常见的知识点,和一些自己的理解。

持续更新中...

PS :

  • 下文中的 \((a, b) = gcd(a, b)\)

1.斐波那契数列

  • \[ f_n = \frac{1}{\sqrt{5}}\left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right] \]
  • \[ \sum_{i = 1} ^ nf_i = f_{n + 2} - 1 \]
  • \[ \sum_{i = 1} ^ n f_{n}^2 = f_{n}f_{n+1} \]
  • \[ \sum_{i = 1} ^ n f_{2i-1} = f_{2n} \]
  • \[ \sum_{i = 1} ^ n f_{2i} = f_{2n + 1} - 1 \]
  • \[ f_{n + m} = f_nf_{m+1}+f_{n-1}f_m \]
  • \[ f_{n-1}f_{n+1} = f_n^2 + (-1)^n \]
  • \[ (f_n, f_m) = f_{(n, m)} \]

2.组合数

  • 多重全排列 : \[ P(n; a_1, a_2,...., a_9) = \frac{n!}{\prod _ i a_i!} \]
  • \(a[i] \in [1, n] ~~and ~~~~\forall i \in [1, k), a[i] \le a[i + 1]\)\(a\) 数组的方案数 \(\binom{n + k - 1}{n}.\)
  • \(n\)个排成一排的物品, 从中取\(m\)个不相邻物品的方案为\(\binom{n - m + 1}{m}\).
  • \(n\)个排成一个圆的物品, 从中去除\(m\)个不相邻物品的方案为\(\binom{n - m + 1}{m} - \binom{n - m - 1}{m - 2}​\), 这个可以由上面这个式子推出来.
  • 范德蒙德卷积1:\(\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}.\)
  • 范德蒙德卷积2:\(\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}.\)

3.欧拉回路

  • 无向图欧拉回路判断 : 所有顶点的度数都为偶数.
  • 有向图欧拉回路判断 : 所有顶点的出度都和入度相等.
  • 无向图有标号欧拉回路计数 : 见 Link.

4.平衡树

  • \(\text{Splay}\)\(\text{pushdown}\) 要将标记清空. \(\text{(Update : 2019.01.29 ~~00 : 20 : 57)}\)
  • \(\text{Splay}\) 无论是在循环替代递归还是递归式(自顶向下遍历时)都要 \(\text{pushdown}\). (\(\text{Update:2019.05.14}\))

5.多项式

  • \(FFT, NTT\) 都是循环卷积.
  • 多项式快速幂, 可以直接 \(O(nlog^2n)\) , 也可以多项式 \(exp + ln\), \(O(nlogn)\) 求, 但是要求多项式的常数项是1(以前\(naive\)).
  • 在取值连续时, 用拉格朗日差值是可以 \(O(n)\) 求点值的, 详见 : Link.
  • \(NTT 或 FFT\) 时如果算的是多个多项式 \(F_i\) 的卷积, 取的点数务必大于等于 \(\sum _ i Deg(F_i).\)

6.数学

  • 泰勒公式 泰勒公式是将一个在 \(x = x_0\) 处具有 \(n\) 阶导数的函数 \(f(x)\) 利用关于 \((x-x_0)\)\(n\) 次多项式来逼近函数的方法。 若函数 \(f(x)\) 在包含 \(x0\) 的某个闭区间 \([a,b]\) 上具有 \(n\) 阶导数,且在开区间 \((a,b)\) 上具有 \((n+1)\) 阶导数,则对闭区间 \([a,b]\) 上任意一点 \(x\) ,成立下式: \[ f(x) = \sum _ {i = 0} ^ {n} \frac{f^{(i)}(x_0)(x - x_0) ^ i}{i !} + R_n(x) \] \(R_n(x)\) 表示泰勒公式的余项。下式也成立: \[ f(x) = \sum _ {i = 0} ^ {+\infty} \frac{f^{(i)}(x_0)(x - x_0) ^ i}{i !} \]

7.矩阵快速幂

  • 如果有多组询问时, 我们直接快速幂的复杂度是\(O(Tm^3logn)\)的, 但是我们可以预处理出转移矩阵的\(2^i\)次幂, 然后直接拿一个\(1 \times m\)的初始矩阵去乘, 复杂度为\(O(m^3logn + Tm^2logn)\), 小Y和恐怖的奴隶主

8.高斯消元

  • 高斯消元处理\(0/1\)矩阵时, 可以用\(bitset\)压一下位, 复杂度为\(O(\frac{m^3}{\omega})\)

  • 在树上消元时, 式子一般可以被表示为 \[ f_i = \sum _ {v \in son_i} f_v + k_if_{fa_i} \to f_i = k_if_{fa_i} + b_i \] \(b_i\)只和\(i\)的儿子节点有关, 所以有 \[ f_i = \left(\sum _ {v \in son_i} {k_vf_i + b_v}\right) +k_if_{fa_i}\\ (1 - \sum _ {v \in son_i}k_v)f_i = \sum _ {v \in son_i}b_v + k_if_{fa_i}\\ f_i = \frac{k_i}{1 - \sum _ {v \in son_i}k_v}f_{fa_i} + \frac{\sum _ {v \in son_i}b_v}{1 - \sum _ {v \in son_i}k_v} \] 又因为叶子节点没有儿子节点, 根节点没有父亲节点, 我们可以直接在递归的过程中把求得的\(k_i, b_i\)往回代入计算就好了, 复杂度\(O(n)\), 时间流逝, 随机游走

9.分块与莫队

  • 有时分完块后, 要对块进行一些预处理, 复杂度可能是\(O(nlogn)\) 的, 这是我们可以通过调整块的大小, 将\(log\) 放到根号里面去, 详见Link
  • 莫队的复杂度主要取决于移动左右指针(修改), 然后查询. 但是显然修改次数是远大于查询次数的, 如果我们用一些查询和修改都是\(O(logn)\)的东西去维护显得不是那么划算, 我们可以用一些查询复杂度较劣, 修改复杂度非常优的东西去维护莫队, 可能会有非常好的效果, 详见Link
  • 有一类莫队题, 修改时可以快速删除加入元素的贡献, 加入元素的贡献复杂度较劣, 我们可以考虑在同一个左端点的询问按右端点降序排列, 并且在每处理一个询问后, 将左端点移到块的最左端, 这样就可以保证可以只删不加, 由于右端点最多移动\(O(n)\)次, 左端点也只会在同一个块中移动, 所以复杂度不变. 反之同样可以. 事情的相似度, 这道题我们要维护一个前驱后继, 如果我们维护一个链表可以支持\(O(1)\)删除, 按照上述做法就很优秀了. 这种莫队常被称作"回滚莫队".
  • 如果把莫队丢到树上, 我们可以直接在\(dfs\)序上操作, 每个点维护一个\(in, out\)时的\(dfs\)序, 可以证明区间内但不在两点路径上的点一定会出现两次, 所以我们维护一下每个元素出现了几次, 如果重复出现就直接算作没有出现就好了 .

10.数论分块

  • 求解一类\(\sum _ {i = 1} ^ n f(\lfloor\frac{n}{i}\rfloor)\)的问题, 我们知道在值域\(n\)内, 不同的\(\lfloor\frac{n}{i}\rfloor\)的值只有\(\sqrt{n}\)个, 可以证明对于\(i\), 最大的使得\(\lfloor\frac{n}{i}\rfloor = \lfloor\frac{n}{j}\rfloor\)\(j\)等于 \[ \left\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor \]
  • 求解一类\(\sum _ {i = 1} ^ n f(\lfloor\frac{n}{i^2}\rfloor)\)的问题时, 不同的的\(\lfloor\frac{n}{i^2}\rfloor\) 的值的个数也很少不会证啊, 可以证明对于\(i\), 最大的使得\(\lfloor\frac{n}{i}\rfloor = \lfloor\frac{n}{j}\rfloor\)\(j\)等于 \[ \sqrt{\left\lfloor\frac{n}{\lfloor\frac{n}{i^2}\rfloor}\right\rfloor} \]

11. Prufer序列

  • \(n\) 个点, \(m\) 个联通块, 每个联通块大小为 \(a_i\) 的森林. 你要加上若干条边, 使得这个森林变成一颗树的方案.

考虑将一个联通块看成一个点, 如果这个点在新的树中的度数为\(d_i\), 方案数为 \(\prod a_i^{d_i}\)

\(q_i\) 为一个 \(prufer\) 序列中 \(i\) 出现的次数, 则有 \[ \begin{aligned} &\sum _ {p} \prod _ {i = 1} ^ m a_i ^ {q_i + 1}\\ &= \left(\prod_ {i = 1} ^ m a_i\right) \sum _ {p} \prod _ {i = 1} ^ {m -2} a_{p_i}\\ &= \left(\prod_ {i = 1} ^ m a_i\right) \prod _ {i = 1} ^ {m - 2} \sum _ {p} ^ m a_{p_i}\\ &= \left(\prod_ {i = 1} ^ m a_i\right)n ^ {m - 2} \end{aligned} \]

方案数为 : \[ \left(\prod_ {i = 1} ^ m a_i\right)n ^ {m - 2} \] 数树

12.反演相关

  • 二项式反演

至多和恰好的转化,设\(f_i\)表示恰好的方案数,\(g_i\)表示至多的方案数,则有: \[ g_n=\sum_{i=0}^n\binom{n}{i}f_i \] 可以用\(g_i\)反演\(f_i\) \[ f_n=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i \] 至少和恰好的转化,设\(f_i\)表示恰好的方案数,\(g_i\)表示至多的方案数,则有: \[ g_k=\sum_{i=k}^n\binom{i}{k}f_i \] 可以用\(g_i\)反演\(f_i\) \[ f_k=\sum_{i=k}^n\binom{i}{k}(-1)^{i-k}g_i \]

  • 子集反演

如果有\(f, g\)满足: \[ g_S=\sum_{T \subseteq S} f_T \] 则有: \[ f_S=\sum_{T \subseteq S}(-1)^{|S|-|T|}g_T \] 或者 \[ g_S=\sum_{S\subseteq T}f_T \] 则有: \[ f_S=\sum_{S \subseteq T} (-1)^{|T|-|S|}g_T \] 其实子集反演和二项式反演本质上是一样的。当每个元素等价时\(f_S\)和集合\(S\)内的东西无关只和\(|S|\)有关,我们可以将子集反演转化成二项式反演。

13.线性筛

  • 用线性筛求每个数的最大最小的质因子,实现\(O(\log n)\)分解每个数。(前提是要\(O(n)\)预处理)

预处理每个数最大质因子代码:

1
2
3
4
5
6
7
8
9
vis[1] = 1;
rep(i, 2, n) {
if(!vis[i]) prime[++cnt] = i, mxpri[i] = i;
for(int j = 1; j <= cnt && prime[j] * i <= n; j++) {
mxpri[prime[j] * i] = mxpri[i];
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}

预处理每个数最小的质因子代码:

1
2
3
4
5
6
7
8
9
vis[1] = 1;
rep(i, 2, n) {
if(!vis[i]) prime[++cnt] = i, mnpri[i] = i;
for(int j = 1; j <= cnt && prime[j] * i <= n; j++) {
mnpri[prime[j] * i] = prime[j];
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}

正确性感性理解一下就好了。