0%

常用知识点及易错点总结

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

持续更新中…

PS :

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

1.斐波那契数列

fn=15[(1+52)n(152)n]f_n = \frac{1}{\sqrt{5}}\left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]

i=1nfi=fn+21\sum_{i = 1} ^ nf_i = f_{n + 2} - 1

i=1nfn2=fnfn+1\sum_{i = 1} ^ n f_{n}^2 = f_{n}f_{n+1}

i=1nf2i1=f2n\sum_{i = 1} ^ n f_{2i-1} = f_{2n}

i=1nf2i=f2n+11\sum_{i = 1} ^ n f_{2i} = f_{2n + 1} - 1

fn+m=fnfm+1+fn1fmf_{n + m} = f_nf_{m+1}+f_{n-1}f_m

fn1fn+1=fn2+(1)nf_{n-1}f_{n+1} = f_n^2 + (-1)^n

(fn,fm)=f(n,m)(f_n, f_m) = f_{(n, m)}

2.组合数

  • 多重全排列 :

P(n;a1,a2,....,a9)=n!iai!P(n; a_1, a_2,...., a_9) = \frac{n!}{\prod _ i a_i!}

  • a[i][1,n]  and    i[1,k),a[i]a[i+1]a[i] \in [1, n] ~~and ~~~~\forall i \in [1, k), a[i] \le a[i + 1]aa 数组的方案数 (n+k1n).\binom{n + k - 1}{n}.
  • nn个排成一排的物品, 从中取mm个不相邻物品的方案为(nm+1m)\binom{n - m + 1}{m}.
  • nn个排成一个圆的物品, 从中去除mm个不相邻物品的方案为(nm+1m)(nm1m2)\binom{n - m + 1}{m} - \binom{n - m - 1}{m - 2}, 这个可以由上面这个式子推出来.
  • 范德蒙德卷积1:i=0k(ni)(mki)=(n+mk).\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}.
  • 范德蒙德卷积2:i=1n(ni)(ni1)=(2nn1).\sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1}.

3.欧拉回路

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

4.平衡树

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

5.多项式

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

6.数学

  • 泰勒公式
    泰勒公式是将一个在 x=x0x = x_0 处具有 nn 阶导数的函数 f(x)f(x) 利用关于 (xx0)(x-x_0)nn 次多项式来逼近函数的方法。
    若函数 f(x)f(x) 在包含 x0x0 的某个闭区间 [a,b][a,b] 上具有 nn 阶导数,且在开区间 (a,b)(a,b) 上具有 (n+1)(n+1) 阶导数,则对闭区间 [a,b][a,b] 上任意一点 xx ,成立下式:

f(x)=i=0nf(i)(x0)(xx0)ii!+Rn(x)f(x) = \sum _ {i = 0} ^ {n} \frac{f^{(i)}(x_0)(x - x_0) ^ i}{i !} + R_n(x)

Rn(x)R_n(x) 表示泰勒公式的余项。下式也成立:

f(x)=i=0+f(i)(x0)(xx0)ii!f(x) = \sum _ {i = 0} ^ {+\infty} \frac{f^{(i)}(x_0)(x - x_0) ^ i}{i !}

7.矩阵快速幂

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

8.高斯消元

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

  • 在树上消元时, 式子一般可以被表示为

fi=vsonifv+kiffaifi=kiffai+bif_i = \sum _ {v \in son_i} f_v + k_if_{fa_i} \to f_i = k_if_{fa_i} + b_i

bib_i只和ii的儿子节点有关, 所以有

fi=(vsonikvfi+bv)+kiffai(1vsonikv)fi=vsonibv+kiffaifi=ki1vsonikvffai+vsonibv1vsonikvf_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}

又因为叶子节点没有儿子节点, 根节点没有父亲节点, 我们可以直接在递归的过程中把求得的ki,bik_i, b_i往回代入计算就好了, 复杂度O(n)O(n), 时间流逝, 随机游走

9.分块与莫队

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

10.数论分块

  • 求解一类i=1nf(ni)\sum _ {i = 1} ^ n f(\lfloor\frac{n}{i}\rfloor)的问题, 我们知道在值域nn内, 不同的ni\lfloor\frac{n}{i}\rfloor的值只有n\sqrt{n}个, 可以证明对于ii, 最大的使得ni=nj\lfloor\frac{n}{i}\rfloor = \lfloor\frac{n}{j}\rfloorjj等于

nni\left\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\right\rfloor

  • 求解一类i=1nf(ni2)\sum _ {i = 1} ^ n f(\lfloor\frac{n}{i^2}\rfloor)的问题时, 不同的的ni2\lfloor\frac{n}{i^2}\rfloor 的值的个数也很少不会证啊, 可以证明对于ii, 最大的使得ni=nj\lfloor\frac{n}{i}\rfloor = \lfloor\frac{n}{j}\rfloorjj等于

nni2\sqrt{\left\lfloor\frac{n}{\lfloor\frac{n}{i^2}\rfloor}\right\rfloor}

11. Prufer序列

nn 个点, mm 个联通块, 每个联通块大小为 aia_i 的森林. 你要加上若干条边, 使得这个森林变成一颗树的方案.

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

qiq_i 为一个 pruferprufer 序列中 ii 出现的次数, 则有

pi=1maiqi+1=(i=1mai)pi=1m2api=(i=1mai)i=1m2pmapi=(i=1mai)nm2\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}

方案数为 :

(i=1mai)nm2\left(\prod_ {i = 1} ^ m a_i\right)n ^ {m - 2}

数树

12.反演相关

  • 二项式反演

至多和恰好的转化,设fif_i表示恰好的方案数,gig_i表示至多的方案数,则有:

gn=i=0n(ni)fig_n=\sum_{i=0}^n\binom{n}{i}f_i

可以用gig_i反演fif_i

fn=i=0n(ni)(1)nigif_n=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}g_i

至少和恰好的转化,设fif_i表示恰好的方案数,gig_i表示至多的方案数,则有:

gk=i=kn(ik)fig_k=\sum_{i=k}^n\binom{i}{k}f_i

可以用gig_i反演fif_i

fk=i=kn(ik)(1)ikgif_k=\sum_{i=k}^n\binom{i}{k}(-1)^{i-k}g_i

  • 子集反演

如果有f,gf, g满足:

gS=TSfTg_S=\sum_{T \subseteq S} f_T

则有:

fS=TS(1)STgTf_S=\sum_{T \subseteq S}(-1)^{|S|-|T|}g_T

或者

gS=STfTg_S=\sum_{S\subseteq T}f_T

则有:

fS=ST(1)TSgTf_S=\sum_{S \subseteq T} (-1)^{|T|-|S|}g_T

其实子集反演和二项式反演本质上是一样的。当每个元素等价时fSf_S和集合SS内的东西无关只和S|S|有关,我们可以将子集反演转化成二项式反演。

13.线性筛

  • 用线性筛求每个数的最大最小的质因子,实现O(logn)O(\log n)分解每个数。(前提是要O(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;
}
}

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