军训前一天随记
本文大致记述了8月到现在我所干的事情,其实就是随便讲讲从1号开始了为期二十天的学校信竞集训,唉,真想自嘲一下,降分保送精英班没用上,还要去学校受苦。
学校在高考方面真的是全省无敌的存在,我也是因为这点才选择了它,但说实话,它的竞赛是真的大芬一托,只能靠自己。槽点太多以至于我不想再吐槽了。
话说明天就要军训了,崭新的高中生话也算开始了,希望自己在高中不要像初中一样是个废物吧。
其实我心里慌得很,毕竟整个暑假都没锻炼
重链剖分
将一棵树剖分成若干条链,使得树上的路径转化为链上的路径,从而将树上的问题转化为链上的问题,这就是树链剖分。而重链剖分是树链剖分的其中一种,其不同点在于剖分的方式。
重链剖分剖分方式重链剖分的剖分方式是:每次选择子树中最大的子树作为重儿子,其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上,出根节点外,链上其他节点都是重儿子的连边构成的链。如下图:
图中的红色边就是重链,而黑色边就是轻链。每个叶子节点也有一条以自己为起点,长度为 $0$ 的重链。
从图中还能看出,每个节点至多只能有一个重儿子。
重链剖分的几个重要数组$de[i]$:编号为 $i$ 节点的深度。
$fa[i]$:编号为 $i$ 节点的父节点。
$hs[i]$:编号为 $i$ 节点的重儿子。
$s[i]$:编号为 $i$ 节点的子树大小。
$dfn[i]$:编号为 $i$ 节点在重链优先遍历序列中的位置。重链优先遍历即先遍历重链,再遍历轻链的遍历方式。这样可以保证在重链上的节点在数组中是连续的,所以可以用线段树等数据结构维护。
$rnk[i]$:重链优先遍历序列中第 $i$ 个节点的编号。$dfn[i]$的下标 ...
倍增法求LCA
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算法
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…$
先单看偶数部分,你就 ...