Flash_plus

知识点总结

好题总结(6) 未归档(3) 杂(1) 游记(1) 题解(40)

/ 注册

全部文章 / 知识点总结（共9篇）

生成函数

生成函数简介生成函数 \(\text{(generating function)}\)，又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。 by wiki 用人话来说生成函数就是把一个序列变成了一个函数。一个形如 \(F(x) = \sum_{n > ...

生成函数

2020-12-27

0 454

数论

数学入门数论快速幂 \(\text{求} a^b \pmod{p}\) \(\text{当b很大的时候显然不能枚举，窝们换一种方法思考}\) \(\text{窝们将b分奇偶讨论}\) \(\text{当b为奇数时,} a ^ b = {a ^ {b / 2}} ^ ...

数论

2020-10-18

0 383

线段树合并

线段树合并前置芝士 —— 动态开点什么是动态开点，是用于处理一些区间跨度比较大，空间比较小的题目。比如： \(1 100000\) 建图，那就和 \(1 2 3 …… 10000\) 一样的内存开销。肯定是不可以直接建，那样空间会炸。所以有 \(2\) 中办法： \(1.\)...

线段树

2020-10-18

0 380

树的重心

树的重心定义树上一节点，且满足它的最大子树的节点数最小。性质 \(ps.\) 性质网上都有，但是没有一篇博客进行了证明。此后的儿子节点指重心与子树相连的节点。 \(1.\) 删除重心后所得的所有子树，节点数不超过原树的 \(\frac{1}{2}\)，一棵树最多有 \(2\) 个重心...

树的重心

2020-10-18

0 320

树的直径

树的直径定义树上的最长简单路。做法 \(1\) 首先我们先随意找定一个点 \(x\) ，然后 \(Dfs\) 求出 \(x\) 在全图中离他最远的节点 \(y\) 再在图中找到离 \(y\) 最远的节点 \(z\) 那么 \(yz\) 的简单路径就是树的直径。证明假设确定了直...

树的直径

2020-10-18

0 553

扩展欧几里得

窝们可以先来看一个式子： \[ax + by = gc d(a,b) \] 根据欧几里得可以得到： \[gcd(a,b) = gcd(b, a \% b) \] 不会欧几里得的同学们可以看这里又根据原式可以推出 : \[gcd(b, a \% b...

数论

2019-12-17

0 399

裴蜀定理

窝们来看一个小知识点：对于一个丢番图⽅程 \(ax + by = m;\) 有解的充要是 \(gcd(a, b) | m\) 至于证明，我觉得大家感性理解一下就行窝们来假设一波：如果 \(gcd(a,b) | m\) 是个伪命题。那么，窝们令 \(c = gcd(a, ...

数论

2019-12-16

0 366

欧几里得

欧几里得 define(定义) \(yygcd(a, b) = c\) 为 \(a, b\) 的公约数。这里的 \(yygcd(a, b)\) 可以理解为 \(gcd(a, b)\)，不过在未证明求出来的公约数就是最大公约数的时候，用 \(yygcd\) 表示，更加严谨。关于欧几里得定理这...

数论

2019-12-12

0 393

博弈论小结

最近学了一点博弈论。来写写blog造福人民(怕自己忘了)希望可以写出一篇比较好懂的文章,这里没有一些绕口的定义，也没有什么麻烦的代码，只有思维上的火花：先来讨论讨论什么是博弈论: 博弈论就是指有若干个人进行一些对弈，并且窝们默认每个人都是最聪明的，不会失误，都可以找到当前的最优解，然后...

博弈论

2019-12-12

0 408