本文大致记述了8月到现在我所干的事情，其实就是随便讲讲从1号开始了为期二十天的学校信竞集训，唉，真想自嘲一下，降分保送精英班没用上，还要去学校受苦。 学校在高考方面真的是全省无敌的存在，我也是因为这点才选择了它，但说实话，它的竞赛是真的大芬一托，只能靠自己。槽点太多以至于我不想再吐槽了。 话说明天就要军训了，崭新的高中生话也算开始了，希望自己在高中不要像初中一样是个废物吧。 其实我心里慌得很，毕竟整个暑假都没锻炼

将一棵树剖分成若干条链，使得树上的路径转化为链上的路径，从而将树上的问题转化为链上的问题，这就是树链剖分。而重链剖分是树链剖分的其中一种，其不同点在于剖分的方式。 重链剖分剖分方式重链剖分的剖分方式是：每次选择子树中最大的子树作为重儿子，其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上，出根节点外，链上其他节点都是重儿子的连边构成的链。如下图： 图中的红色边就是重链，而黑色边就是轻链。每个叶子节点也有一条以自己为起点，长度为 $0$ 的重链。 从图中还能看出，每个节点至多只能有一个重儿子。 重链剖分的几个重要数组$de[i]$：编号为 $i$ 节点的深度。 $fa[i]$：编号为 $i$ 节点的父节点。 $hs[i]$：编号为 $i$ 节点的重儿子。 $s[i]$：编号为 $i$ 节点的子树大小。 $dfn[i]$：编号为 $i$ 节点在重链优先遍历序列中的位置。重链优先遍历即先遍历重链，再遍历轻链的遍历方式。这样可以保证在重链上的节点在数组中是连续的，所以可以用线段树等数据结构维护。 $rnk[i]$：重链优先遍历序列中第 $i$ 个节点的编号。$dfn[i]$的下标 ...

LCA (Least Common Ancestors)，即为最近公共祖先，求LCA也是求树上两点最短路的重要一环。 朴素算法求LCA首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲12345678910111213int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } while (depth[u] > depth[v]) { u = parent[u]; } while (u != v) { u = parent[u]; v = parent[v]; } return u;} 倍增法求LCA思路大致与朴素算法相同，但跳转时不是一次跳一个父亲，而是跳$2^k$个父亲，跳深度较大的节点时$k$为最大的满足$2^k \leq depth[u]-depth[v]$的数。而共同跳转时，$k$从大到小 ...

BSGS算法是一种用于解决离散对数问题的算法，它的全称是Baby Step Giant Step，意为小步大步。然而我并不知到为什么要叫这个名字 离散对数问题假设有一个同余方程$a^x \equiv b \pmod m$，其中$a,b,m$都是给定的整数，$a$与$m$互素。如何求解$x$的值？ 第一个想法可能是暴力枚举，将$x$从$0$开始枚举到$m-1$，直到找到一个满足方程的$x$。时间复杂度是$O(m)$，如果$m$很大就挂了。 BSGS算法既然暴力不行，那么我们就要想办法降低时间复杂度。BSGS算法就是一种优化的算法，它的时间复杂度是$O(\sqrt{m})$。它的思想也很简单。 首先我们令$x=A\sqrt{m}-B$，其中$A,B$是两个整数且$0\leq A,B\leq \sqrt{m}$。那么原方程就变成了$a^{A\sqrt{m}-B} \equiv b \pmod m$，即$a^{A\sqrt{m}} \equiv b\cdot a^B \pmod m$。 我们可以将方程分解为两个方程: \begin{cases} c \equiv b\cdot a^B \pm ...

乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 $a$ 和 $m$ 互质，那么 $a$ 关于模 $m$ 的乘法逆元 $a^{-1}$ 存在，且满足 $a \times a^{-1} \equiv 1 \pmod m$。 本文主要讲解乘法逆元的四种求法。 费马小定理方法费马小定理表明对于任意整数 $a$ 和素数 $p$，有 $a^{p-1} \equiv 1 \pmod p$。由此我们可以推出 $a \times a^{p-2} \equiv 1 \pmod p$，所以 $a^{p-2}$ 就是 $a$ 关于模 $p$ 的乘法逆元。接下来我们就可以通过快速幂的方法求出 $a^{p-2}$。但要注意的是，这个方法只适用于模数是素数的情况。 123456789LLI qpow(LLI a,LLI b,LLI p){ LLI ans=1; while(b){ if(b&1)ans=ans*a%p; a=a*a%p; b>>=1; } return ans;} ...

欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 $ax+by=c$ 的整数解的算法，是欧几里得算法的升级版，也是提高的数论内容中的重要算法之一。 这个算法的原理是利用欧几里得算法求解最大公约数的过程中，不断地更新 $x$ 和 $y$ 的值，直到求解出整数解。具体的过程如下： 设 $a$ 和 $b$ 为两个整数，$d = \gcd(a, b)$，则有 $ax+by=d$。我们可以通过欧几里得算法求出 $d$。 设 $a = b \times k + r$，则有 $d = \gcd(b, r)$，且 $d = bx’+ry’$。将 $r$ 代入，有 $d = bx’+(a-bk)y’$，整理得 $d = ay’+b(x’-ky’)$。因此，我们可以通过递归的方式求解 $x$ 和 $y$。 1234567891011LLI exgcd(LLI a,LLI b,LLI &x,LLI &y){ if(b==0){ x=1,y=0; return a; } LLI d=e ...

线段树真的是一种挺折磨人的数据结构，但它的应用范围也是非常广泛的。它可以在 $O(\log n)$ 的时间内完成区间修改和区间查询。似乎有句话是这么说的：树状数组能做的，线段树都能做；线段树能做的，树状数组不一定能做。 线段树的操作线段树是一种二叉树，它的每一个节点都代表了一个区间。对于一个区间 $[l, r]$，它的左儿子代表了 $[l, mid]$，右儿子代表了 $[mid+1, r]$。其中 $mid = \frac{l+r}{2}$。 依然以区间和为例。 建立通常来说线段树的建立是以递归进行的，由于后面会涉及到区间修改等操作，所以我通常用一个结构体来存储线段树的信息。1234567891011121314struct{ LLI l,r,sum;}d[4*N];//4倍空间，不然存不下void build(LLI l,LLI r,LLI p){ d[p].l=l,d[p].r=r; if(l==r){//直接存储数值 d[p].sum=a[l]; return; } LLI m=l+((r-l)>>1); buil ...

二十天左右的集训结束了，虽然学校的教学完全学不到任何东西，但得承认通过自学学到了不少东西。 自学的第一个知识就是树状数组，它可以在 $O(\log n)$ 的时间内完成单点修改和前缀和查询。由于码量奇少，在搭配上差分数组和权值数组，就能实现许多骚操作。 树状数组的结构以下以维护区间和为例。假设使用$c[i]$数组作为树状数组，它存储了原数组的某一段区间和。右端点是 $i$，左端点是 $i - lowbit(i) + 1$，其中 $lowbit(i)$ 是 $i$ 的二进制表示中最低位的 $1$ 的位置。比方说 $6 = (110)_2$，那么 $lowbit(6) = 2 = (10)_2$。 在树状数组中，每一个 $c[i]$ 都指向父亲 $c[i+lowbit(i)]$。在区间和的情况下，$c[i]$ 存储了 $[i-lowbit(i)+1, i]$ 的区间和。比如 $c[4]$ 存储了 $[1, 4]$ 的区间和。如下图所示： 其中每一层$c[i]$都等于它的子节点之和与原数组以$i$为下标的数值之和，即$c[i] = a[i]+\sum_{j=i-lowbit(i)+1}^{i ...

中考，代表了一个初中生三年的目标。就在昨天考完后，整个身体都放松了下来，想到未来两个月的暑假，我同样充满了期待。然而伴随我的竟然还有空虚感，不过想想也是，当前的目标已经完成，未来的目标仍然遥远，换了谁都会有这种感觉吧。距离上一篇文章已经过去差不多8个月了，不敢相信时间过得这么快，到这里又想起三年初中的点点滴滴，说实话真有点舍不得。 小学毕业那天的事我已经差不多全忘了，只记得周围的人不知道为什么哭和那天的毕业餐很难吃，我几乎是不带一点感情就毕业了。然而初中却不同，这三年，我第一次感受到了精神上有价值的友谊，第一次明白了学习到底是什么，第一次明白和我一样有实力的大有人在。这三年，肯定带来的比小学六年多得多。我想这就是舍不得的原因吧。 今天是中考结束后的第二天，7月3号。距离毕业典礼，我作为一个初中生的日子还剩九天。

最近开始思考起了阶乘加速的问题，深入思考了一下，得到了一些有趣的想法。 尝试1：分治既然阶乘最朴素的算法都是$O(n)$的，那么最直接的想法就是把$n$踢掉，在塞个$\log{n}$之类进去，自然就是分治了。 想法1第一个想法是每次从中间切开，分成 $1\times2\times3\times…\times \frac{n}{2}$ 和 $(\frac{n}{2}+1)\times(\frac{n}{2}+2)\times(\frac{n}{2}+3)\times…\times n$ 两部分，然后递归求解。但这样，子问题的性质好像发生了改变，虽然它俩都是求区间积，但一个是从1开始，而一个是从$\frac{n}{2}+1$开始，并非求阶乘，就让人很难受，所以我立马放弃了这个想法。 其实是我想半天也没想出怎么处理子问题 想法2第二个想法差点让我相信它就是我想要的答案了，同样是分成两部分，FFT给了我一点启发，这次我把奇数和偶数分成两组：$1\times3\times5\times7\times…$ 和 $2\times4\times6\times8\times…$ 先单看偶数部分，你就 ...