From zxy的思维技巧 而来。 传送门 这真是一道套路的好题啊。 首先要计算二元组 (a,b) 的个数，看数据范围肯定枚举一个 a ，然后计算所有满足的 b ，最后求和后除以 2 。 然后具体的考虑怎么计算所谓 b 的个数，考虑一个点 u ，
重链剖分剖分方式 重链剖分的剖分方式是：每次选择子树中最大的子树作为重儿子，其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上，出根节点外，链上其他节点都是重儿子的连边构成的链。如下图： 图中的红色边就是重链，而黑色边就是轻链。每个叶子节点也有一条以自己为起点，长度为 0 的重链。 从图
朴素算法求LCA 首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲 int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } while (depth[u
离散对数问题 假设有一个同余方程a^x \equiv b \pmod m，其中a,b,m都是给定的整数，a与m互素。如何求解x的值？ 第一个想法可能是暴力枚举，将x从0开始枚举到m-1，直到找到一个满足方程的x。时间复杂度是
乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 a 和 m 互质，那么 a 关于模 m 的乘法逆元 a^{-1} 存在，且满足 a \times a^{-1} \equiv 1 \pmod m。 本文主要讲解乘法逆元的四种求法。 费马小定理方法 费马小定理表明对于任意整数 a 和素数 p，
欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 ax+by=c 的整数解的算法，是欧几里得算法的升级版，也是提高的数论内容中的重要算法之一。 这个算法的原理是利用欧几里得算法求解最大公约数的过程中，不断地更新 x 和 y 的值，直到求解出整数解。具体的过程如下：
线段树真的是一种挺折磨人的数据结构，但它的应用范围也是非常广泛的。它可以在 O(\log n) 的时间内完成区间修改和区间查询。似乎有句话是这么说的：树状数组能做的，线段树都能做；线段树能做的，树状数组不一定能做。 线段树的操作 线段树是一种二叉树，它的每一个节点都代表了一个区间。对于一个区间 [l
二十天左右的集训结束了，虽然学校的教学完全学不到任何东西，但得承认通过自学学到了不少东西。 自学的第一个知识就是树状数组，它可以在 O(\log n) 的时间内完成单点修改和前缀和查询。由于码量奇少，在搭配上差分数组和权值数组，就能实现许多骚操作。 树状数组的结构 以下以维护区间和为例。假设使用c[
中考，代表了一个初中生三年的目标。就在昨天考完后，整个身体都放松了下来，想到未来两个月的暑假，我同样充满了期待。然而伴随我的竟然还有空虚感，不过想想也是，当前的目标已经完成，未来的目标仍然遥远，换了谁都会有这种感觉吧。 距离上一篇文章已经过去差不多8个月了，不敢相信时间过得这么快，到这里又想起三年初
看网上的个人博客，手痒也弄了一个。 姑且是搞完了，用的是经典的 github pages+hexo 方案。 放个彩叭 🎉 要写什么我也不知道， 甚至可能吃灰， 不过重要的是折腾的过程嘛。
发布于 2024-08-29
![[ZJOI2019] 语言](/upload/70937229p0.png)
