https://wiki.cvbbacm.com/ 2026-04-29T23:41:38+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2021-08-22T15:16:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E4%B8%87%E8%83%BD%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95&rev=1629616565&do=diff 万能欧几里得算法 算法简介 一种 $O(\log n)$ 计算形如 $f(n)=\sum_{i=1}^n \lfloor \frac {ai+b}c \rfloor$ 的函数的算法。 算法原理 不妨考虑待计算函数就是 $f(n)=\sum_{i=1}^n \lfloor \frac {ai+b}c\rfloor$，同时假设 $b\lt c$，考虑按如下过程计算 $f(n)$。 考虑在 $(0,n]$ 范围内逐渐增加 $x$，当 $y=\frac {ax+b}c$ 恰好等于某个整数时 $y\gets y+1$$U$$x$$\text{ans}\gets \text{ans}+y$$R$$U$$R$$f(n)$$y=\frac {ax+b}c(x\in (0,n])$$S$$g(a,b,c,n,U,R)$$y=\frac {ax+b}c(x\in (0,n])$$S$$S^k=S^{k-1}S$$a\ge c$$R$$\lfloor \frac ac\rfloor$$U$$\lfloor \frac ac\rfloor$$U$$R$$$ g(a,b,c,n,U,R)=g(a\bm… text/html 2021-05-26T14:16:11+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E4%B8%89%E5%85%83%E7%8E%AF%E8%AE%A1%E6%95%B0&rev=1622009771&do=diff 三元环计数 算法例题 例题一 洛谷p1989 题意 给定 $n$ 个点和 $m$ 条边的无向图。定义三元环为满足所有点两两之间有连边的三元组数，求图中的三元环数。 题解 将无向图转化为有向图，其中每条边由原图中度数小的点指向度数大的点，当两个点度数相同时由编号小的点指向编号大的点。$(u,v,w)$$u\to v,u\to w,v\to w$$u$$u\to w$$w$$v$$v\to w$$w$$O(\sum_{i=1}^m\text{out}_{v_i})$$\text{deg}_{v_i}\le \sqrt m$$\text{out}_{v_i}\le \sqrt m$$\text{deg}_{v_i}\gt \sqrt m$$v_i$$\text{deg}_w\ge \text{deg}_{v_i}\gt \sqrt m$$w$$\sqrt m$$\text{out}_{v_i}\le \sqrt m$$O\left(m\sqrt m\right)$$n$$m$$(A,B,C,D)$$AB,BC,CD,DA,AC$$c_i$$\sum_{i=1}^n {c_i\… text/html 2020-08-21T11:08:49+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E4%BA%8C%E9%A1%B9%E5%BC%8F%E5%8F%8D%E6%BC%94&rev=1597979329&do=diff 二项式反演 算法简介 一种特殊反演，主要应用于组合计数。 算法思想 $$f(n)=\sum_{i=m}^n{n\choose i}g(i)\iff g(n)=\sum_{i=m}^n(-1)^{n-i}{n\choose i}f(i)$$ $$f(n)=\sum_{i=n}^m{i\choose n}g(i)\iff g(n)=\sum_{i=n}^m(-1)^{i-n}{i\choose n}f(i)$$ 算法例题 例题一 题意 求错排数 $D_n$。 题解 考虑任意排列，有 $n!$ 种，其中恰有 $i$ 封信错排的方案数为 ${n\choose i}D_i$，于是 $n!=\sum_{i=0}^n{n\choose i}D_i$。 $D_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}i!$$n$$k$$f(k)$$k$$f(k)={n\choose k}2^{2^{n-k}}$$g(k)$$k$$f(k)$$g(i)(i\ge k)$${i\choose k}$$f(k)=\sum_{i=k}^n{i\choose k}g(i)$… text/html 2021-01-28T20:37:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92_1&rev=1611837443&do=diff 动态规划 1 数位DP 算法简介 一般用于处理形如区间 $[l,r]$ 中满足条件的数有几个之类问题。 算法思想 首先考虑将区间 $[l,r]$ 拆分成 $[0,r]-[0,l]$。 考虑记忆化搜索，一般搜索函数为 $f(pos,s,eq,zero)$。 其中 $pos$ 表示当前搜索位置，$s$$eq$$zero$$[l,r]$$2$$s$$[l,r]$$0\sim 9$$0\sim 9$$s$$a,b$$[a,b]$$\text{Mod}$$\text{dp}$$\text{Mod}$$18\ast(18\ast 9)^2$$18\ast(18\ast 9)^3\approx 8\times 10^7$$\text{dp}$$10$$2$$[l,r]$$1\le l\le r\lt 10^{1000}$$10^9+7$$2$$2$$3$$2$$2$$3$$0\le A\le B\le N$$S(A)\gt S(B)$$(A,B)$$S(n)$$n$$f(pos,d,eq1,eq2)$$d$$S(B)-S(A)$$eq1$$B$$eq2$$A$$B$$B,A$$pos$… text/html 2021-02-11T18:58:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92_2&rev=1613041122&do=diff 动态规划 2 二进制优化 题意 洛谷p1776 给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$，重量为 $w_i$，数量为 $c_i$。求最多可以得到的价值。 题解 暴力方法为将每种物品转化为 $c_i$ 个独立物品考虑，然后就是一个 $01$$c_i$$1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$$1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$$O\left(\sum_{i=1}^n \log {c_i}\right)$$O\left(m\sum_{i=1}^n \log {c_i}\right)$$n$$1$$n$$1$$m$$a_i$$t_i$$x$$b_i-\vert a_i-x\vert$$d$$1$$\text{dp}(i,j)$$t_i$$j$$$ \text{dp}(i,j)=\max_{j-d(t_i-t_{i-1})\le k\le j+d(t_i-t_{i-1})}\text{dp}(i-1,k)+b_i-\vert a_i-j\vert $$$O(nm)$$m$$n$$v_i$$w_… text/html 2021-01-14T20:28:23+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92_3&rev=1610627303&do=diff 动态规划 3 树形背包问题 基本模型 给定一棵 $n$ 阶树，每个结点拥有重量 $w_i$ 和价值 $v_i$，且选取某个结点必须选取该结点的父结点。 给定背包容量 $M$，问可以得到的最大价值。 $\text{dfs}$ 序优化 $\text{dp}(i,j)$$i$$j$$i$$[i-sz_i+1,i]$$i$$i$$i$$$ \text{dp}(i,j)=\max(\text{dp}(i-sz_i,j),\text{dp}(i-1,j-w_i)+v_i) $$$O(nm)$$1$$n$$f_i$$v_i$$dp(i,j)$$i$$j$$\text{LCA}$$O(n^2)$$dp(1,i)\ge 0$$i$ text/html 2021-07-14T19:27:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92_4&rev=1626262052&do=diff 动态规划 4 四边形不等式优化 定义 区间包含单调性：$\forall l_1\le l_2\le r_1\le r_2\to f(l_2,r_1)\le f(l_1,r_2)$。 四边形不等式：$\forall l_1\le l_2\le r_1\le r_2\to f(l_1,r_1)+f(l_2,r_2) \le f(l_2,r_1)+f(l_1,r_2)$。 类型一 $$ f_{l,r}=\min_{k=l}^{r-1}(f_{l,k}+f_{k+1,r})+w(l,r) $$ 性质一 若 $w(l,r)$ 满足区间包含单调性和四边形不等式，则 $f(l,r)$ 满足四边形不等式。 性质二 记 $g(l,r)$ 为最小最优决策点，即 $f_{l,g(l,r)}+f_{g(l,r)+1,r}=\min_{k=l}^{r-1}(f_{l,k}+f_{k+1,r})$$f(l,r)$$g(l,r-1)\le g(l,r)\le g(l+1,r)$$g(l,r)$$\sum_{l=1}^n\sum_{r=l+1}^n g(l+1,r)-g(l,r-1)=\sum_{… text/html 2021-02-19T17:40:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8A%A8%E6%80%81dp&rev=1613727639&do=diff 动态 DP 用于解决一些 $\text{dp}$ 递推式简单但需要支持修改的问题，时间复杂度为 $O(nk^3\log n)$，其中 $k$ 为递推式的相关项。 例题一 CF1380F 题意 给定一个长度为 $n$ 的十进制数 $D$。 设 $a_i$ 表示 $A$ 从低到高的第 $i$ 位，其他定义类同。$A+B$$\{a_n+b_n\cdots a_2+b_2,a_1+b_1\}$$3248+908=\{3+0,2+9,4+0,8+8\}=\{3,11,4,16\}=311416$$q$$D$$(A,B)$$A+B=D$$\text{dp}$$\text{dp}(i)$$A+B=D[1,i]$$d_i$$\text{dp}(i)\gets (d_i+1)\text{dp}(i-1)$$d_i$$\text{dp}(i)\gets [10\le d_id_{i-1}\le 18](19-d_id_{i-1})\text{dp}(i-2)$$$ \begin{bmatrix}(d_i+1) & [10\le d_id_{i-1}\le 18](19-d_id_{i-1}) … text/html 2020-08-17T15:23:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_1&rev=1597648980&do=diff 可持久化线段树 算法简介 一种可以维护历史版本的线段树，时间复杂度和空间复杂度均为 $O\left(n+m\log n\right)$。 算法思想 显然如果对每个历史版本都重建线段树保存时间复杂度和空间复杂度均为 $O\left(nm\right)$。 但如果可以重复利用部分结点信息，则可以降低时间复杂度和空间复杂度。$O\left(\log n\right)$$n$$O\left(n+m\log n\right)$$n$$m$$k$$k$$a[1\sim n]$$a[i]$$[l,r]$$r$$l-1$$a[l\sim r]$$k$$O\left(n+m\log n\right)$$n$$i$$m$$a$$b$$k$$a$$b$$O\left(n+m\log^2 n\right)$$O\left(n+m\log n\right)$… text/html 2020-07-27T22:57:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_2&rev=1595861854&do=diff 可持久化平衡树 算法简介 一种可以维护历史版本的平衡树，时间复杂度和空间复杂度均为 $O\left(m\log n\right)$。 算法思想 使用类似可持久化线段树的方法继承历史版本，但大部分平衡树都自带旋转操作，节点的父子关系会发生，不利于可持久化。$\text{fhq treap}$$\text{fhq treap}$$\text{split}$$\text{merge}$$\text{split}$$\text{merge}$$\text{merge}$$\text{fhq treap}$$\text{split}$$\text{merge}$$\text{split}$$\text{merge}$$\text{merge}$… text/html 2020-09-20T19:30:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_3&rev=1600601427&do=diff 可持久化字典树 算法简介 一种可以维护历史版本的字典树，实现方面与可持久化线段树类似，主要用于维护区间异或和。 时间复杂度和空间复杂度均为 $O\left(m\log n\right)$。 算法例题 洛谷p4735 题意 给定序列 $a_1,a_2\cdots a_n$，支持下述操作：$x$$l,r,x$$\max_{l \le p\le r} x\oplus(a_p\oplus a_{p+1}\oplus \cdots \oplus a_N)$$N$$S_i=a_1\oplus a_2\oplus \cdots \oplus a_i$$\max_{l-1\le p\le r-1} x\oplus S_N\oplus S_p$${S_0,S_1,S_2\cdots S_n}$$x\oplus S_N$$n$$a_i\oplus a_j$$i,j\in [l,r]$$a_i$$a_l,a_{l+1}\cdots a_r$$a_i$$O(n\log v)$$n$$k$$k$$i$$[0,i-1]$$i$$k_i$$(k_i,i)$$i$$[0,k_i-1]$$[k_i+1,i… text/html 2020-08-01T00:05:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9B%BE%E8%AE%BA_1&rev=1596211503&do=diff 图论 1 最短路 非负权边单源最短路 $\text{Dijkstra}$ 算法板子 时间复杂度 $O(m\log m)$。 template <typename T> struct dijkstra{ T dis[MAXN]; bool vis[MAXN]; priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q; void solve(int src,int n){ mem(vis,0); _rep(i,1,n) dis[i]=Inf; dis[src]=0; q.push(make_pair(dis[src],src)); while(!q.empty()){ pair<T,int> temp=q.top();q.pop(); int u=temp.second; if(vis[u]) continue; vis[u]=true; for(int i=head[u];i;i=edge[i].next){ i… text/html 2021-08-15T16:45:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9B%BE%E8%AE%BA_2&rev=1629017148&do=diff 图论 2 网络流 最大流 $\text{EdmondsKarp}$ 算法 每次通过 $\text{bfs}$ 找到一条边数最少的增广路。 $\text{bfs}$ 时间复杂度 $O(m)$，最多增广 $O(nm)$ 次，总时间复杂度 $O(nm^2)$。 const int MAXN=205,MAXM=5005,Inf=0x7fffffff; struct Edge{ int to,cap,next; Edge(int to=0,int cap=0,int next=0){ this->to=to; this->cap=cap; this->next=next; } }edge[MAXM<<1]; int head[MAXN],edge_cnt; void Clear(){mem(head,-1);edge_cnt=0;}//边从0开始编号 void Insert(int u,int v,int c){ edge[edge_cnt]=Edge(v,c,head[u]); head[u]=edge_cnt++; edge[edge_cnt]=Edg… text/html 2020-07-27T22:59:20+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9B%BE%E8%AE%BA_3&rev=1595861960&do=diff 图论 3 网络流经典例题 方格取数问题 洛谷p2774 题意 给定一个 $n\times m$的方格图，每个方格中都有一个正整数。 现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。$\inf$$n$$m$$i$$p_i$$j$$c_j$$V$$V$$V$$V$$V$$\inf$$=$$-$$(S,T)$$s$$t$$S$$T$$(u,v)\subset E,u\in S,v\in T$$u$$v$$(u,v)\subset E,u\in S$$v\in S$$T$$T_1$$S$$S_1$$T$$S_2$$C(S,T)=T_1+S_2$$W=S_1-S_2$$C(S,T)+W=T_1+S_1$$W=T_1+S_1-C(S,T)$$T_1+S_1$$C(S,T)$$\inf$$\text{DAG}$$0$$n$$0$$n$$1$$1$$1$$n$$1,2,3,\cdots$$\text{DAG}$$0$$0$$n$$n$$m$$1$$n$$1$$-1$$1$$0$$2$$2$$n=2$$2$$\text{dp}$$O(nm)$$n$$X… text/html 2021-08-07T20:41:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9C%86%E6%96%B9%E6%A0%91&rev=1628340065&do=diff 广义圆方树 算法简介 一种可以将图的简短路径操作转化为树上路径操作的算法。 算法实现 首先给出圆方树相关定义： 对无向图求双连通分量，然后给每个双连通分量建一个新点。 特别的，这里点双连通分量的定义是不存在割点的最大子图，然后只有一个点的图需要自行特殊处理。$O(n)$$(s,c,f)$$s,c,f$$s$$c$$f$$(s,c,f)$$s$$c$$f$$s,f$$c$$s,f$$s,f$$-1$$s,f$$c$$s,f$$\text{dp}$$O(n+m)$$u$$v$$\text{set}$$O\left(n\log^2 n\right)$$O(n)$$O(n\log n)$$\text{LCA}$$S$$c$$c\not\in S$$c$$S$$c$$u,v$$c$$u,v$$S$$S$$\text{LCA}$$\text{dfs}$$2$$O(n\log n)$$2$$3$$2$$2$$\text{Tarjan}$$\text{LCA}$$\text{LCA}$… text/html 2021-09-04T21:41:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9F%BA%E4%BA%8E%E5%80%BC%E5%9F%9F%E9%A2%84%E5%A4%84%E7%90%86%E7%9A%84%E5%BF%AB%E9%80%9F_gcd&rev=1630762917&do=diff 基于值域预处理的快速 GCD 算法简介 $O(V)$ 预处理 $O(1)$ 查询 $\text{gcd}$。 算法实现 首先考虑将每个数 $n$ 分解成 $a,b,c$，满足 $a\le b\le c$ 且若 $c\gt \sqrt n$ 则 $c$ 一定是质数。 利用线性筛处理上述过程，线性筛会枚举 $n$ 的最小素因子 $p$，假设 $\frac np$$a',b',c'$$n$$a'p,b',c'$$p\le n^{\frac 14}$$a'\le (\frac np)^{\frac 13}$$a'p\le \sqrt n$$p\gt n^{\frac 14}$$p$$n$$n$$a'=1$$a'p$$gcd(x,y)$$y=abc$$x,a$$x$$a$$b,c$$gcd(x,a)=gcd(x\bmod a,a)$$a$$\sqrt V$$a$$O(V)$$\sqrt V$$\text{gcd}$$O(1)$… text/html 2021-07-17T09:26:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%9F%BA%E7%8E%AF%E6%A0%91&rev=1626485160&do=diff 基环树 算法简介 基环树由普通树额外增加一条边组成，是图论经典问题之一。 算法例题 例题一 CF711D 题意 给定一个有向图(不保证连通)，每个点有一条出边。问有多少种方案能将边重定向，使得图中不存在有向环。$i$$w_i$$$ 2^{n-\sum w_i}\prod (2^{w_i}-2) $$$n$$w_i$$i$$p_i$$(u,v)$$u$$v$$\text{dp}$$(u,v)$$-\text{inf}$$\text{dp}$$\neq$$d$$s$$(u,v)$$$ \max(d(u)+d(v)+\text{dis}(u,v),d(u)+d(v)+s-\text{dis}(u,v)) $$$\text{dis}(u,v)=\text{pre}(u)-\text{pre}(v)$$\text{max}$$O(n)$$2$$(u,v)$$$ \min(d(u)+d(v)+\text{dis}(u,v),d(u)+d(v)+s-\text{dis}(u,v)) $$$\max(d(u)+d(v)+\text{dis}(u,v))$$rt$$rt$$O(n^2)$$… text/html 2021-09-05T08:46:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%90%8C%E4%BD%99%E6%9C%80%E7%9F%AD%E8%B7%AF&rev=1630802777&do=diff 同余最短路 算法简介 用于计算 $k_1a_1+k_2a_2+\cdots +k_na_n$ 在 $[0,m]$ 范围内能表示的数的算法。 算法实现 考虑建点 $0,1\cdots a_1-1$。然后对每个点 $i$，连边 $i\to (i+a_j)\bmod a_1(w=a_j)$，再跑最短路。 于是可以 $O(n\times a\log a)$ 计算出最小的可以表示成 $ka_1+r(0\le r\lt a_1)$ 的数，于是每个 $r$ 对答案的贡献为 $\lfloor \frac {m-\text{dis}(r)}{a_1}\rfloor$$a$$a_1$$k$$w$$\text{dis}(i,j)$$i$$2w$$j$$\{\text{dis}(2,r)+2kw|0\le r\lt 2w,k\ge 0\}$$r$$2w$$2$$T$$n,k$$n$$k$$1$$k$$50$$n$$k$$1$$n$$k$$O(\sqrt k)$$k$$O\left(\frac {\sqrt k}{\ln k}\right)$$k=1$$k$$k\mid n$$k$$a,b$$ax+b… text/html 2020-10-02T11:02:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%90%89%E5%8F%B8%E6%9C%BA%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1601607752&do=diff 吉司机线段树 算法简介 一种支持区间最值修改及各种查询的线段树。 算法模板 模板一 HDU5306 题意 给定一个序列，支持下述三种操作： * 对 $l\le i\le r$，$a_i=\min(a_i,v)$ * 询问区间 $[l,r]$ 的最大值 * 询问区间 $[l,r]$ 的和 题解 $v$$v$$v$$\text{dfs}$$\text{dfs}$$O(\log n)$$O(n\log n)$$O((n+m)\log n)$$l\le i\le r$$a_i=a_i+v$$l\le i\le r$$a_i=\min(a_i,v)$$[l,r]$$[l,r]$$[l,r]$$1\sim 4$$O(\log n)$$O(\log n)$$O(\log n)$$O(\log^2 n)$$O(n\log n+m\log^2 n)$$1,3,4,5$$1\sim 5$$O(n\log n+m\log^2 n)$$n$$[l,r]$$[l,r]$$i\in [l,r],a_i=a_i+v$$i\in [l,r],a_i=v$$O(n+q\log n)$$A$… text/html 2021-08-29T18:56:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%BA%94%E7%94%A8&rev=1630234607&do=diff 多项式应用 习题一 洛谷p3702 题意 询问有多少序列满足下列条件： * 序列长度等于 $n$ * 序列由不超过 $m$ 的正整数构成且至少含有一个素数 * 序列所有数之和是 $p$ 的倍数 题解 考虑容斥，于是答案为由不超过 $m$$m$$m$$p$$i$$m$$p$$i$$\text{dp}(i,j)$$i$$p$$j$$+$$\text{NTT}$$O(m+p\log n\log p)$$p\le 100$$O(m+p^2\log n)$$A,B$$A$$|A|=m,|B|=n$$$ f(x)= \begin{cases} x-a &x= a\sim z\\ 0 &x=* \end{cases} $$$c_i=\sum_{j=0}^{m-1}\left(f(a_j)-f(b_{i-m+1+j})\right)^2f(a_j)f(b_{i-m+1+j})$$B$$i$$m$$A$$c_i=0$$t_i=a_{m-1-i}$$$\sum_{x+y=i}\left(f(t_x)-f(b_y)\right)^2f(t_x)f(b_y)=\sum_{x+y=i}… text/html 2020-08-03T22:45:37+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%A4%9A%E9%A1%B9%E5%BC%8F_1&rev=1596465937&do=diff 多项式 1 拉格朗日插值法 算法简介 给定 $n$ 个坐标 $(x_i,y_i)$，求解唯一确定的最高次不超过 $n-1$ 次的多项式 $f(x)$，满足 $f(x_i)=y_i$。 算法模板 洛谷p4781 构造 $g_i(x)=y_i\prod_{j\neq i}\frac {x-x_j}{x_i-x_j}$，易知 $$g_i(x_j)= \begin{cases} y_i, & j=i \\ 0, & j\neq i \end{cases}$$ 于是有 $$f(x)=\sum_{i=1}^n g_i(x)=\sum_{i=1}^n y_i\prod_{j\neq i}\frac {x-x_j}{x_i-x_j}\tag{1}$$ 根据上式可以 $O(n^2)$ 计算出 $f(k)$。 int x[MAXN],y[MAXN]; int Lagrange(int n,int k){ int ans=0,a,b; _rep(i,1,n){ a=y[i],b=1; _rep(j,1,n){ if(j==i)continue; a=1LL*… text/html 2021-05-02T17:40:19+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%A4%9A%E9%A1%B9%E5%BC%8F_2&rev=1619948419&do=diff 多项式 2 FFT 算法简介 $O(n\log n)$ 时间实现多项式点值表示法与系数表示法之间的转化，主要用于加速多项式乘法。 算法实现 假设 $f(x)$ 为 $n-1$ 次多项式，且 $n$ 是 $2$ 的幂次。(如果不满足条件可以将高次系数视为 $0$$O(n\log n)$$f(x)=a_0+a_1x+a_2x^2+\cdots a_{n-1}x^{n-1}$$g(x)=a_0+a_2x+\cdots a_{n-2}x^{\frac n2-1},h(x)=a_1+a_3x+\cdots a_{n-1}x^{\frac n2-1}$$f(x)=g\left(x^2\right)+xh\left(x^2\right)$$\omega_n=\cos \frac {2\pi}n+\sin \frac {2\pi}ni$$x=\omega_n^k,x=\omega_n^{k+\frac n2}(k=0,1\cdots \frac n2-1)$$$f(\omega_n^k)=g(\omega_n^{2k})+\omega_n^kh(\omega_n^{2k})=g(\omega… text/html 2020-08-25T12:43:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%A4%9A%E9%A1%B9%E5%BC%8F_3&rev=1598330596&do=diff 多项式 3 倍增 FFT 算法简介 主要用于加速可以倍增转移的动态规划，时间复杂度 $O\left(n\log^2 n\right)$。 算法例题 CF755G 题意 将 $n$ 个球排成一排。规定一个组至少包含一个球，至多包含两个相邻的球，且一个球至多属于一个组。$n$$k$$998244353$$\text{dp}(i,j)$$i$$j$$n$$n-1$$$\text{dp}(i,j)=\text{dp}(i-1,j)+\text{dp}(i-1,j-1)+\text{dp}(i-1,j-2)$$$a+b$$1\sim a$$a+1\sim a+b$$a,a+1$$$\text{dp}(a+b,k)=\sum_{i=0}^k\text{dp}(a,i)\text{dp}(b,k-i)+\sum_{i=0}^{k-1}\text{dp}(a-1,i)\text{dp}(b-1,k-i-1)$$$F_n(x)=\sum_{i=0}^{\infty} \text{dp}(n,i)x^i$$$F_n(x)=F_{n-1}(x)+xF_{n-1}(x)+x^2F_{n-2}(x… text/html 2020-08-25T17:43:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%A4%9A%E9%A1%B9%E5%BC%8F_4&rev=1598348607&do=diff 多项式 4 循环卷积 定义 $$c_k=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j$$ 性质 对序列 $A,B$ 做长度为 $n$ 的 $\text{FFT}$ 等价于求序列 $A,B$ 的长度为 $n$ 的循环卷积。 考虑单位根反演证明 $$ \begin{equation}\begin{split} c_k&=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j\\ &=\frac 1n\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{d=0}^{n-1}w_n^{d(i+j-k)}a_ib_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}w_n^{di}a_iw_n^{dj}b_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\left(\sum_{i=0}^{n-1}a_iw_n^{di}\righ… text/html 2020-08-27T11:38:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%AD%97%E7%AC%A6%E4%B8%B2_1&rev=1598499528&do=diff 字符串 1 KMP 算法 算法简介 给定两个字符串 $S_1,S_2$，查询 $S_2$ 在 $S_1$ 中出现的位置。时间复杂度 $O(|S_1|+|S_2|)$。 算法实现 洛谷p3375 定义字符串 $S$ 的前缀函数 $f$ 表示 $S$ 的最长的相等的真前缀和真后缀，先考虑计算模式串 $S_2$ 的 $f$$f(i+1)$$s[1,i]$$f(i)$$$s_1s_2\cdots s_{f(i)}s_{f(i)+1}\cdots s_{i-f(i)+1}s_{i-f(i)+2}\cdots s_is_{i+1}$$$s[1,f(i)]=s[i-f(i)+1,i]$$s_{i+1}=s_{f(i)+1}$$f(i+1)=f(i)+1$$s_{i+1}\neq s_{f(i)+1}$$j$$s[1,j]=s[i-j+1,i]=s[f(i)-j+1,f(i)]$$j$$s[1,f(i)]$$j=f(f(i))$$j=0$$j$$1$$1$$|s_2|$$O(|s_2|)$$O(|s_1|)$$O(|s_1|+|s_2|)$$abcabcabc$$f(n)=6$$f(6)$… text/html 2020-10-01T20:08:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%AD%97%E7%AC%A6%E4%B8%B2_2&rev=1601554138&do=diff 字符串 2 AC 自动机 算法简介 一种用于多模式串匹配的自动机，可以近似看成 $\text{Trie}$ 树上的 $\text{KMP}$ 算法。 算法例题 例题一 洛谷p5357 题意 给你一个文本串 $S$ 和 $n$ 个模式串 $T_i$，求每个模式串 $T_i$ 在 $S$ 中出现的次数。$\text{AC}$$\text{fail}$$O(|S|+\sum_{i=1}^n |T_i|)$$n$$01$$S_i$$S_i$$\text{AC}$$S_i$$\text{fail}$$\text{fail}$$\text{dfs}$$\text{dfs}$$O(\sum_{i=1}^n |S_i|)$$S$$B,P$$T$$S$$s_i$$T$$s_i$$B$$T$$s_i$$P$$T$$q$$i$$j$$\text{fail}$$i$$p_i$$j$$p_j$$\text{Trie}$$p_j$$p_i$$\text{fail}$$\text{Trie}$$\text{dfs}$$\text{Trie}$$\text{fail}$$\text{dfs}$$O((… text/html 2020-09-02T10:52:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%AD%97%E7%AC%A6%E4%B8%B2_3&rev=1599015147&do=diff 字符串 3 后缀数组(SA) 算法简介 后缀树的一种替代品，可以用于解决各种字符串问题。 算法实现 后缀数组的核心为 $sa$ 数组，$rk$ 数组以及 $\text{height}_i$ 数组。 其中 $sa_i$ 表示排名为 $i$ 的后缀的起始位置，$rk_i$ 表示起始位置为 $i$$sa$$O(n\log n)$$rk_{sa_i}=i$$O(n)$$rk$$\text{height}_i$$\text{LCP}(S[sa_i,n],S[sa_{i-1},n])$$$\text{height}_{rk_i}\ge \text{height}_{rk_{i-1}}-1$$$\text{height}_{rk_i}=\text{LCA}(S[i,n],S[sa_{rk_i-1},n]),\text{height}_{rk_{i-1}}=\text{LCP}(S[i-1,n],S[sa_{rk_{i-1}-1},n])$$S[i-1,i-1+k]=S[j,j+k]$$S[i,i-1+k]=S[j+1,j+k]$$O(n)$$\text{height}_i$$$\text… text/html 2020-09-04T11:28:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%AD%97%E7%AC%A6%E4%B8%B2_4&rev=1599190116&do=diff 字符串 4 后缀自动机(SAM) 简介 一种用于解决各种字符串问题的数据结构，时间复杂度 $O(n)$。 性质 性质一：$\text{SAM}$ 是一张有向无环图，$t$ 为 $s$ 子串当且仅当存在唯一从原点出发的路径使得该路径等价于 $t$。$O(|T|)$$T$$S$$s$$t$$\text{endpos}$$s$$t$$\text{endpos}$$\text{SAM}$$\text{parent}$$\text{endpos}$$L$$R$$L$$\text{endpos}$$L$$\text{endpos}(L)$$L$$\text{endpos}(L)$$L'$$S$$|L|-|L'|$$|R|=|L'|+1$$S$$i$$i$$i$$L'$$|R|=i+1$$i$$i$$\text{endpos}$$\text{endpos}\gt i$$c+L'$$O(n)$$\text{endpos}$$S$$S$$S$$1$$\text{SAM}$$O(n)$$\text{SA}$$\text{height}$$\text{height}$$O(n\log n)$$S$… text/html 2020-10-21T22:53:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E5%B7%A6%E5%81%8F%E6%A0%91&rev=1603292018&do=diff 左偏树 算法简介 一种可并堆，支持 $O(\log n)$ 的 $\text{push}$、$\text{pop}$、$\text{merge}$ 操作。 算法思想 定义外节点为左儿子或右儿子为空的节点，$\text{dist}_i$ 表示节点 $i$ 到其子树中最近外节点的距离。 规定空节点的 $\text{dist}$ 为 $-1$。左偏树的定义为对每个节点 $u$$\text{dist}_\text{lson}\ge \text{dist}_\text{rson}$$\text{dist}_u=\text{dist}_\text{rson}+1$$\text{dist}_u\sim O(\log \text{sz}_u)$$\text{dist}_u=\max(\text{dist}_\text{lson},\text{dist}_\text{rson})+1=\text{dist}_\text{rson}+1$$\text{dist}_u$$u$$u$$\text{dist}_u$$\text{dist}_u$$\text{dist}_u+1$$\text{sz}_u… text/html 2020-10-02T12:14:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%8B%93%E5%B1%95%E5%9F%9F%E5%B9%B6%E6%9F%A5%E9%9B%86&rev=1601612045&do=diff 拓展域并查集 算法简介 一种通过拆点来处理点与点之间关系的并查集。 算法例题 洛谷p1525 题意 给定 $n$ 个点，$m$ 条带权边。要求将所有点划分为两个点集，输出所有两端点都在同一集合的边权的最大值的最小可能值。$\text{A},\text{B}$$2n$$i$$i\in \text{A}$$i+n$$i\in \text{B}$$1\le i\le n$$u\to v$$u$$v+n$$u\in \text{A}$$v\in \text{B}$$v+n\to u$$u\to v$$u$$v$$u\in \text{A}$$v\in \text{A}$$A,B,C$$A$$B$$B$$C$$C$$A$$n$$A,B,C$$m$$X$$Y$$X$$Y$$i$$i\in A$$i+n$$i\in B$$i+2n$$i\in C$$X$$Y$$X\to Y,X+n\to Y+n,X+2n\to Y+2n$$(X,Y+n)$$(X+n,Y)$$X$$Y$$X\to Y+n,X+n\to Y+2n,X+2n\to Y$$(X,Y)$$(X+n,Y)$… text/html 2021-08-11T10:20:25+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%9B%BF%E7%BD%AA%E7%BE%8A%E6%A0%91&rev=1628648425&do=diff 替罪羊树 算法简介 一种平衡树，思维简单，码量少，速度还行，而且没有旋转操作。 算法思想 首先替罪羊树的插入类似普通的二叉搜索树，删除操作就是打上删除标记。 但只有这样显然不能保证替罪羊树的平衡度。$O(n)$$O(\log n)$$\text{sz}$$\text{tot}$$\alpha$$\alpha\ast\text{sz} \lt \max(\text{sz}_{lson},\text{sz}_{rson})$$\alpha$$\alpha$$\alpha$$0.7 \sim 0.8$$\beta$$0.4$$\beta\ast\text{tot} \gt \text{sz}$ text/html 2021-01-23T22:13:08+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%9C%80%E5%B0%8F%E6%96%AF%E5%9D%A6%E7%BA%B3%E6%A0%91&rev=1611411188&do=diff 最小斯坦纳树 算法简介 一种用于计算只含图中部分关键节点的最小生成树的算法。 算法实现 考虑状压 $\text{dp}$，第一维表示当前包含节点的点集，第二维表示树根节点。考虑两步转移 $$ \text{dp}(s,u)\gets \min_{k\subset s}(\text{dp}(k,u)+\text{dp}(s\oplus k,u)) $$ $$ \text{dp}(s,u)\gets \min(\text{dp}(s,u),\text{dp}(s,v)+w) $$ 时间复杂度据说是 $O(2^kn^3+3^kn)$$p$$c_i$$c_i$$g(s)$$s$$s'$$1\le i\le p$$c_i\in s$$g(s)$$\min_{1\le u\le n}dp(s',u)$$g(s)\gets \min_{k\subset s}(g(k)+g(s\oplus k))$… text/html 2021-07-14T15:51:10+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%9D%8E%E8%B6%85%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1626249070&do=diff 李超线段树 算法简介 一个支持动态加入折线段和查询某个区间内所有折线段最高/最低点的数据结构。 算法模板 全局修改单点查询 洛谷p4254 题意 支持以下两种操作： * 加入直线 $y=kx+b$ * 询问当前所有直线在 $x_0$$O(q\log n)$$(x_0,y_0)\to (x_1,y_1)$$x=x_0$$O(\log n)$$O\left(q\log^2 n\right)$$(x,y_0)\to (x,y_1)$$(x,\max(y_0,y_1))$$w(u)=\max(w(u),a\times \text{dis}(u,s)+b)(u\in s\to t)$$\max(w(u))(u\in s\to t)$$d(u)$$u$$p=\text{LCA}(s,t)$$u\in p\to s$$\text{dis}(u,s)=d(s)-d(u)$$w(u)=-a\times d(u)+b+a\times d(s)$$u\in p\to t$$\text{dis}(u,s)=d(s)+d(u)-2d(p)$$w(u)=a\times d(u)+b+a\t… text/html 2021-07-30T20:18:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%94%AF%E9%85%8D%E6%A0%91&rev=1627647524&do=diff 支配树 算法简介 给定一个有向图，定义一个超级源点，连向所有入度为 $0$ 的点。 对于点对 $(u,v)$，如果删除 $u$ 将导致超级源点不可以到达 $v$，则称 $u$ 支配 $v$。 易知支配关系构成树，其中每个子树的根节点支配子树的所有结点。称这样的树为支配树。$v$$u_1,u_2,u_3\cdots u_k\to v$$v$$u_1,u_2\cdots u_k$$\text{LCA}$$u$$p(u)$$u$$p(u)\to u$$u\to v$$p(v)\to \text{LCA}(p(v),u)$$p(u)$$0$$\text{LCA}(p(u),0)=p(u)$$\text{LCA}$$O(m\log n)$$1$… text/html 2021-02-11T16:20:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BC%98%E5%8C%96%E5%BB%BA%E5%9B%BE&rev=1613031616&do=diff 数据结构优化建图 算法例题 例题一 CF786B 题意 $n$ 个点的有向图。给定 $3$ 中连边方式，分别为： * $u$ 向 $v$ 连一条边权为 $w$ 的边 * $u$ 向 $[l,r]$ 每个节点连一条边权 $w$ 的边 * $[l,r]$ 向 $u$ 每个节点连一条边权 $w$ 的边$s$$[1,n]$$0$$u$$v$$u$$v$$0$$v$$u$$v$$u$$[1,n]$$2,3$$O(\log n)$$O(m\log^2 n)$$n$$(a,b,c,d)$$[a,b]$$[c,d]$$1$$u,v$$[a,b]\to u$$v\to [c,d]$$0$$u\to v$$1$$01\text{bfs}$$O(m\log n)$ text/html 2020-10-08T15:00:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%BB%83%E4%B9%A0_1&rev=1602140433&do=diff 数据结构练习 1 线段树合并/分裂 习题一 洛谷p2824 题意 给定由 $1\sim n$ 的排列构成的序列 $A$，要求支持以下下两种操作： * 将 $A_{l\sim r}$ 按升序排列 * 将 $A_{l\sim r}$ 按降序排列 $m$ 次操作后询问位置 $p$ 上的数值。 题解 考虑初始时构造 $n$$[i,i](1\le i\le n)$$[l,r]$$[l,b]$$[a,b]$$[a,l-1],[l,b]$$[c,d]$$[c,r],[r+1,d]$$[l,b]\cdots [c,r]$$O(n\log n)$$O(n\log n)$$O(\log n)$$O(\log n)$$[p,p]$$\text{dfs}$$O(\log n)$$O((n+m)\log n)$$1$$2$$i$$i$$v$$p$$1-p$$1$$m$$V_i$$i$$D_i$$i$$$\sum_{i=1}^m iV_iD_i^2$$$D(i,j)$$i$$j$$\text{dfs}$$D$$1$$0$$D$$i$$$D(u,i)=\left(D(l,i)\left(p… text/html 2020-07-27T22:56:09+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E8%AE%BA_1&rev=1595861769&do=diff 数论 1 逆元递推 算法简介 线性时间递推 $0\sim p-1$ 在模 $p$ 意义下的乘法逆元。 算法思想 首先 $1^{-1}\equiv 1\pmod p$。 设 $p=k\ast i+r\left(1\le r \lt i\lt p\right)$。 所以有 $k\ast i+r\equiv 0\pmod p$。 两边同乘以 $r^{-1}$、$i^{-1}$，有 $i^{-1}\equiv -k\ast r^{-1}\pmod p$。 即 $i^{-1}\equiv -\lfloor \frac pi\rfloor\ast (p\ \text{mod}\ i)^{-1}\pmod p$ 算法模板 洛谷p3811 const int MAXP=3e6+5; int inv[MAXP]; void get_inv(int p){ inv[1]=1; _for(i,2,p) inv[i]=1LL*(p-p/i)*inv[p%i]%p; } $\sum_{i=1}^n a_if(\lfloor \frac ni\rfloor)$$a_i$$O(\s… text/html 2020-07-27T22:56:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E8%AE%BA_2&rev=1595861778&do=diff 数论 2 前置公式 \begin{equation}\left(\sum_{d\mid n}f(x)\right)\left(\sum_{d\mid m}g(x)\right)=\sum_{d_1\mid n}\sum_{d_2\mid m}f(d_1)g(d_2)\tag{1}\end{equation} \begin{equation}\sum_{m=1}^n\sum_{d\mid (n,m)}f(d)=\sum_{d\mid n}\frac{f(d)n}d\tag{2}\end{equation} \begin{equation}\sum_{x\mid n}\left(f(x)\sum_{y\mid\frac nx}g(y)\right)=\sum_{y\mid n}\left(g(y)\sum_{x\mid\frac ny}f(x)\right)\tag{3}\end{equation} 可积函数 一般可积函数 定义 数论函数 $\theta$ 被定义为可积函数，若 $(a)\ \exists n\left(\theta(n)\ne 0\right)$ $(… text/html 2020-07-27T22:57:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E8%AE%BA_3&rev=1595861872&do=diff 数论 3 杜教筛 算法简介 一种 $O\left(n^{\frac 23}\right)$ 计算积性函数前缀和的算法。 算法思路 设 $f$、$g$ 为积性函数，$S(n)=\sum_{i=1}^n f(i)$，考虑 $f$、$g$ 的狄利克雷卷积的前缀和 \begin{equation}\sum_{i=1}^n (f\ast g)(i)=\sum_{i=1}^n\sum_{d\mid i}f(\frac id)g(d)=\sum_{d=1}^n \left(g(d)\sum_{k=1}^{\lfloor\frac nd\rfloor}f(k)\right)=\sum_{d=1}^n g(d)S(\lfloor\frac nd\rfloor)\end{equation} 所以有 \begin{equation}\sum_{i=1}^n (f\ast g)(i)=g(1)S(n)+\sum_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)\end{equation} 移项得 \begin{equation}g(1)S(n)=\sum_{i=1… text/html 2020-09-23T09:11:40+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E8%AE%BA_4&rev=1600823500&do=diff 数论 4 Min_25筛 算法简介 一种 $O\left(\frac {n^{\frac 34}}{\log n}\right)$ 计算积性函数 $F(x)$ 前缀和的算法。 算法思路 首先给定 $\text{Min_25}$ 筛的适用条件：$F(p)$ 的值可以拆分为若干个完全积性函数 $f(p)$，且 $\sum f(x)$ 可以快速计算。 设 $\text{midv}(x)$ 表示 $x$ 的最小素因子。将所有素数从小到大排列，记为 $p_1,p_2,p_3\cdots$$f(x)$$f(p)=F(p)$$g(n,k)=\sum_{i=1}^n[\text{midv}(i)\gt p_k\text{ or } i\in \text{prime}]f(i)$$g(n,k-1)$$g(n,k)$$\text{midv}(i)=p_k$$i\not\in \text{prime}$$f(i)$$p_k^2\ge n$$i$$p_k$$i'=\frac i{p_k}$$\text{midv}(i')\ge p_k,f(i')=\frac {f(i)}{f(p_k)}$$f(p… text/html 2020-10-16T15:01:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B0%E8%AE%BA_5&rev=1602831707&do=diff 数论 5 卢卡斯定理 算法简介 $O(p+\log_pn)$ 计算 ${n\choose m}\bmod p$ 的算法，$p$ 为素数。 算法实现 $${p\choose i}=\frac pi{p-1\choose i-1}$$ 于是对 $1\le i\le p-1$，有 ${p\choose i}\equiv 0\pmod p$。 $$(1+x)^p\equiv {p\choose 0}+{p\choose 1}x+\cdots +{p\choose p}x^p\equiv 1+x^p\pmod p$$ 对 ${n\choose m}$，不妨设 $n=k_1p+r_1,m=k_2p+r_2$，于是有 $$(1+x)^n\equiv (1+x)^{k_1p+r_1}\equiv ((1+x)^p)^{k_1}(1+x)^{r_1}\equiv (1+x^p)^{k_1}(1+x)^{r_1}\pmod p$$ 对比左右两边 $x_m$ 的系数，有 $${n\choose m}\equiv {k_1\choose k_2}{r_1\choose r_2}\pmod… text/html 2020-07-30T18:48:24+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%95%B4%E4%BD%93%E4%BA%8C%E5%88%86&rev=1596106104&do=diff 整体二分 算法简介 一种同时对所有询问进行二分答案的离线算法，时间复杂度一般为 $O(n\log n\log v)$。 算法例题 动态区间第 $k$ 小 洛谷p2617 题意 给定一个长度为 $n$ 的序列，支持两种操作： * 表示查询下标在区间 $[l,r]$$k$$x$$y$$2$$mid$$x$$mid$$mid$$r$$i$$k_i\le r$$i$$i$$k_i$$r$$v\le mid$$2$$2$$2$$n\times n$$q$$k$$k$$O\left(n^2\log^3 n\right)$$m$$k$$[l,r]$$p_i$$p_i$$[l,r](l\gt r)$$[l,m],[1,r]$$+$$+$$O(m\log m)$$O(m\log m)$$O(\log m)$$O(m\log^2 m)$$O(m\log m)$… text/html 2020-08-22T21:24:55+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%96%AF%E7%89%B9%E6%9E%97%E6%95%B0&rev=1598102695&do=diff 斯特林数 第一类斯特林数 定义 第一类斯特林数 $\begin{bmatrix}n\\ k\end{bmatrix}$ 表示将 $n$ 个不同元素构成 $m$ 个圆排列的方案。 性质一 $$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$ 考虑新加入的数 $n$，要么单独成环，要么插入到其他环中，其中插入方式有 $n-1$ 种。 性质二 $$x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i$$$x^{\overline n}$$$x^{\overline {n+1}}=x^{\overline n}(x+n)=(x+n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i=\sum_{i=0}^{n+1} \left(\begin{bmatrix}n\\ i-1\end… text/html 2021-08-11T10:37:14+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%97%A0%E6%97%8Btreap&rev=1628649434&do=diff $\text{fhq treap}$ 算法简介 $\text{Treap}$ 的无旋版本，支持快速分裂、合并以及可持久化。 算法思想 $\text{Treap}$ 保证深度的方法为给每个结点赋随机的优先级 $r$，权值方面 $\text{Treap}$ 为二叉搜索树，优先级方面 $\text{Treap}$ 为堆。 而当每个点的权值 $val$$r$$r$$\text{Treap}$$\text{fhq treap}$$\text{Treap}$$O(\log n)$$\text{split}$$\text{merge}$$\text{split}$$\text{split}$$v$$\text{fhq treap}$$\text{split}$$k$$\text{Treap}$$O(\log n)$$\text{split}$$\text{sz}$$\text{fhq treap}$$\text{merge}$$r$$\text{merge}$$k1$$k2$$\text{Treap}$$O(\log n)$$\text{split}$$\text{merge}$… text/html 2020-07-28T20:31:27+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%A0%91%E4%B8%8A%E5%90%AF%E5%8F%91%E5%BC%8F%E5%90%88%E5%B9%B6&rev=1595939487&do=diff 树上启发式合并 算法简介 一种离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。 算法思想 首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。$\text{dfs}$$O(\log n)$$O(\log n)$$O(n\log n)$$1$$n$$1$$a,b$$a$$b$$26$$dfs$$n$$1\sim n$$1$$n$$1$$n$$d(u,x)$$u$$u$$x$$k$$d(u,k)$$1$$n$$a\sim v$$0$$2$$O(cn\log n)$$O(2^c)$$c$ text/html 2020-08-16T11:05:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%A0%91%E5%90%8C%E6%9E%84&rev=1597547157&do=diff 树同构 无根树同构 对每棵树，至多只有两个重心。显然两棵无根树同构等价于以两个无根树的某个重心为根的两个有根树同构。 于是无根树同构问题可以转化为有根树同构问题，故下面只考虑有根树同构问题。$O(n)$$$h_{1,u}=\text{sz}_u+\sum_{v\in \text{son}(u)}\text{sz}_vh_{1,v}$$$$h_{2,u}=\text{sz}_u+\text{sz}_u\sum_{v\in \text{son}(u)}\text{sz}_vh_{2,v}$$$f\{1,2\cdots n\}\to \{p_1,p_2\cdots p_n\}$$\text{sz}_u$$p_{\text{sz}_u}$$p$$01$$\text{Trie}$$O(n)$$O(n^2)$$d$$d+1$$d+1$$0$$d$$O(n)$$\text{dp}$$\text{set}$$\text{dp}$$\text{set}$$O(n\log n)$$\text{dp}$$\text{dp}(u_1,u_2)$$u1,u2$$v1,v2$$\text{dp}(v_1,v… text/html 2020-07-30T14:23:30+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E6%A0%91%E5%A5%97%E6%A0%91&rev=1596090210&do=diff 树套树 树状数组套树状数组 简介 一般用与维护二维矩阵，码量以及常数小，通常涉及差分。 模板题 洛谷p4514 维护一个矩阵，支持以下操作： * 将以 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素加上 $k$ * 输出 $(r_1,c_1),(r_2,c_2)$ 为顶点的矩阵内全部元素的和$a_{x,y}=\sum_{i=1}^x\sum_{j=1}^y b_{i,j}$\begin{equation}S_{i,j}=\sum_{x=1}^r\sum_{y=1}^c a_{x,y}=\sum_{x=1}^r\sum_{y=1}^c\sum_{i=1}^x\sum_{j=1}^y b_{i,j}=\sum_{i=1}^r\sum_{j=1}^c (r-i+1)(c-j+1)b_{i,j}\end{equation}\begin{equation}S_{i,j}=(r+1)(c+1)\sum_{i=1}^r\sum_{j=1}^c b_{i,j}-(c+1)\sum_{i=1}^r\sum_{j=1}^c ib_{i,j}-(r+1)\sum_{… text/html 2021-08-29T15:58:52+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%8C%AB%E6%A0%91&rev=1630223932&do=diff 猫树 算法简介 一种 $\text{ST}$ 表的进阶数据结构。支持 $O(n\log n)$ 预处理，$O(n)$ 修改，$O(1)$ 查询。 算法实现 考虑分治处理每个区间询问 $[ql,qr]$ 的过程。设当前分治区间为 $[L,R]$，左区间为 $[L,M]$，右区间为 $[M+1,R]$。 如果 $[ql,qr]\subseteq [L,M]$ 或 $[ql,qr]\subseteq [M+1,R]$，则递归处理。否则一定有询问左端点位于左区间，右端点位于右区间。$O(n\log n)$$[ql,qr]$$ql$$qr$$\text{LCA}$$10100$$10001$$\text{LCA}$$10$$\text{LCP}$$\log2(n)$$\text{LCA}$$O(1)$$2$$O(n\log n)$$O(\frac n2+\frac n4+\frac n8+\cdots)\sim O(n)$$[l_1,r_1]$$[l_2,r_2]$$l_1\le l_2,r_1\le r_2$$l_2\lt r_1$… text/html 2020-07-27T22:59:30+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%9F%A9%E9%98%B5%E6%A0%91%E5%AE%9A%E7%90%86&rev=1595861970&do=diff 矩阵树定理 算法简介 一种生成树的计数定理，时间复杂度 $O\left(n^3\right)$。 算法实现 无向图 定义生成树的权值为所有该生成树中所有边权的乘积，则有如下结论： 邻接矩阵 $D$ 中 $d_{i,i}=$ 所有与节点 $i$ 相连的边的权值和，$d_{i,j}=0(i\neq j)$$L$$d_{i,j}=edge[i][j].w$$d_{i,j}=d_{j,i}$$K=D-L$$K'$$K$$i$$i$$i$$det(K')=$$1$$L$$D$$d_{i,i}=$$i$$K'$$K$$i$$i$$det(K')=$$i$$D$$d_{i,i}=$$i$$K'$$K$$i$$i$$det(K')=$$i$$n$$m$$t$$1$$10^9+7$$n$$n$$n\times n$$p_{i,j}$$i,j$$p_{i,j}=p_{j,i},p_{i,i}=0$$p_{i,j}$$i,j$$E$$T$\begin{equation}P=\sum_T\prod_{e\in E-T}(1-p_e)\prod_{e\in T}p_e=\prod_{e\in E}(… text/html 2020-07-27T22:54:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%82%B9%E5%88%86%E6%A0%91&rev=1595861690&do=diff 点分树 算法简介 点分治的动态版本，可以动态维护树上路径信息，一般会与线段树或平衡树等数据结构配合使用。 特别适用于一些需要维护与路径长度相关信息的题目。 一般空间复杂度为 $O(n\log n)$$O\left(\log^2 n\right)$$\log n$$n\log n$$\log n$$\log n$$\log n$$n\log n$$n\log n$$\text{fa}$$O\left(\log^2 n\right)$$n$$1$$m$$x$$k$$x$$y$$x、y、k$$x$$x$$k$$x$$x$$k$$\text{dist}(x,y)$$x$$y$$\text{ST}$$x$$k$$\text{fa}$$\text{fa}$$k-\text{dist}(x,fa)$$\text{fa}$$\text{fa}$$k-\text{dist}(x,fa)$$O\left(\log^2 n\right)$$x$$0$$x$$0$$\text{fa}$$\text{fa}$$\text{dist}(x,fa)$$\text{fa}$$\text{dist}(x,fa)… text/html 2020-08-21T20:48:57+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0_1&rev=1598014137&do=diff 普通生成函数(OGF) 算法简介 形如 $F(x)=\sum_{n=0}^{\infty}a_nx^n$ 的函数， $a_n$ 可以提供关于这个序列的信息，一般用于解决无标号组合计数问题。 算法例题 例题一 洛谷p2000 题意 已知如下约束条件： * $6\mid a$ * $b\le 9$ * $c\le 5$ * $4\mid d$ * $e\le 7$ * $2\mid f$ * $0\le g\le 1$$8\mid h$$10\mid i$$j\le 3$$a+b+c+d+e+f+g+h+i+j=n$$1+x^6+x^{12}+\cdots=\frac 1{1-x^6}$$1+x+x^2+\cdots +x^9=\frac {1-x^{10}}{1-x}$$1+x+x^2+\cdots +x^5=\frac {1-x^6}{1-x}$$1+x^4+x^8+\cdots=\frac 1{1-x^4}$$1+x+x^2+\cdots +x^7=\frac {1-x^8}{1-x}$$1+x^2+x^4+\cdots=\frac 1{1-… text/html 2020-08-21T18:02:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0_2&rev=1598004120&do=diff 指数生成函数(EGF) 算法简介 形如 $F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!}$ 的函数， $a_n$ 可以提供关于这个序列的信息，一般用于解决有标号组合计数问题。 基本运算 $$F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!},G(x)=\sum_{n=0}^{\infty}b_n\frac {x^n}{n!}$$ $$F(x)G(x)=\sum_{n=0}^{\infty}\sum_{i=0}^n a_ib_{n-i}\frac {x^n}{i!(n-i)!}=\sum_{n=0}^{\infty}\sum_{i=0}^n {n\choose i}a_ib_{n-i}\frac {x^n}{n!}$$ $$\sum_{n=0}^{\infty}k^n\frac {x^n}{n!}=e^{kx},\sum_{n=0}^{\infty}n^{\underline k}\frac {x^n}{n!}=x^ke^x$$ 算法例题 例题一 洛谷p5748 题意 定义贝尔数 $w_n$ 表… text/html 2020-07-27T22:56:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91&rev=1595861786&do=diff 笛卡尔树 算法简介 一种二叉树，主要用于解决有关序列 $\text{RMQ}$ 问题和直方图问题，建树时间复杂度 $O(n)$。 算法思想 笛卡尔树具有如下三条性质： * 对笛卡尔树中序遍历可以得到原序列 * 笛卡尔树的点权符合堆性质$\text{RMQ}$$\text{LCA}$$\text{Treap}$$O(n)$$N$$a_i$$k$$N$$f(i,j)$$i$$j$$H$$\text{sz}$$g(i,j)$$i$$j$$k$$n\times m$$k$$k!C_n^kC_m^k$$k!$$k!$\begin{equation}H=H_u-H_{fa},\text{sz}_u=1+\text{sz}_{lson}+\text{sz}_{rson}\end{equation}\begin{equation}g(u,i)=\sum_{j=0}^i f(\text{lson},j)\times f(\text{rson},i-j)\end{equation}\begin{equation}f(u,i)=\sum_{j=0}^i g(u,j)\times (i-j)… text/html 2020-10-01T10:45:47+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%BA%BF%E6%80%A7%E5%9F%BA&rev=1601520347&do=diff 线性基 算法简介 一个用长度为 $\log v$ 的数组维护值域为 $[1,v]$ 的序列的异或和的数据结构。 插入一个值和查询第 $k$ 小值的时间复杂度均为 $O(\log v)$。 算法思想 线性基本质就是高斯消元，把需要维护的序列的所有数用二进制表示，得到一组 $\log v$$k$$2^{k}-1$$0$$k$$k$$k$$q$$u$$v$$O\left(\log^2 v\right)$$v$$LCA$$O\left((n+q)\log n \log^2 v\right)$$O\left((q+n\log v)\log n + q\log^2 v\right)$$\text{A}$$\text{B}$$\text{B}$$k$$\text{B}$$2^{|\text{A}|-k}$$\text{P}$$\text{C}\subset \text{A}-\text{P}$$v\in \text{B}$$v$$\text{C}$$\text{P}$$v$$\text{C}$$\text{P}$$\text{C}$$\text{C}$$2^{|\text{A}|-k}$… text/html 2020-10-03T11:38:13+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%88%86%E6%B2%BB&rev=1601696293&do=diff 线段树分治 算法简介 一种将修改和询问操作转移到线段树上，最后通过遍历线段树求解的离线算法。 算法例题 洛谷p5787 题意 初始给定 $n$ 个点，图上没有边。现有 $m$ 条边，每条边出现的时间为 $[l_i,r_i]$。询问每个时刻图是否为二分图。$O(m\log n)$$O(m\log^2 n)$$n$$m$$k_i$$i$$j$$i$$j$$i$$i'$$j'$$i'$$j$$q$$x$$y$$-1$$-1$$O\left((q+\sum_{i=1}^n k_i)\log q\log n\right)$$n$$1\sim n$$v_i$$m$$s$$v$$l,r,d,x$$x$$t$$[l,r]$$[t-d+1,t]$$0$$O(\log v)$$O((n+m)\log v)$$O((n+m)\log v\log m)$$1$$1$$L\le 1000$$\text{dfs}$$\text{bitset}$$1,2,3$$O\left(\cfrac {(m+q)L^2\log q}w\right)$$O\left(\cfrac {(m+q)L^2}w\right)… text/html 2021-07-14T15:53:29+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%90%88%E5%B9%B6_%E5%88%86%E8%A3%82&rev=1626249209&do=diff 线段树合并/分裂 算法简介 一种快速合并、分裂线段树(一般为权值线段树)的算法，时空间复杂度 $O(m\log n)$。 算法思想 更新、分裂线段树时动态开点，易知更新操作时空间复杂度 $O(\log n)$。 关于分裂操作，遇到空结点则返回。其余操作同线段树查询，遇到分裂区间的子区间则将原节点转移给新节点，然后返回。$O(\log n)$$\text{return}$$O(m\log n)$$n$$m$$x,y,z$$x$$y$$z$$0$$\text{MLE}$$O(m\log^2 n)$$O(m\log n)$$n$$1 \sim n$$x$$k$$-1$$u$$v$$1$$2$$O(n\log n)$$n$$m$$i$$s_i$$t_i$$i$$w_i$$u$$s\to \text{LCA}(s,t)\to t$$s\to \text{LCA}(s,t)$$u\in \{s\to \text{LCA}(s,t)\}$$w_u=d_s-d_u$$\text{LCA}(s,t)\to t$$u\in \{\text{LCA}(s,t)\to t\}$$\text{dist… text/html 2021-02-07T19:17:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E8%8E%AB%E9%98%9F%E7%AE%97%E6%B3%95_1&rev=1612696624&do=diff 莫队算法 1 普通莫队 算法模型 只有询问操作，共 $m$ 个询问，每个询问操作都是一个区间 $[l_i,r_i]$。询问区间范围为 $[1,n]$。 可以 $O(1)$ 根据当前维护区间 $[l,r]$ 更新到 $[l-1,r],[l,r+1],[l+1,r],[l,r-1]$。 则利用莫队可以 $O(n\sqrt m)$ 离线处理所有询问。 算法实现 $[1,n]$$S$$kS\lt l_i\le (k+1)S$$r_i$$r_i$$O(n)$$O\left(\frac {n^2}S\right)$$O(S)$$O(mS)$$O\left(\frac {n^2}S+mS\right)$$S\sim O\left(\frac n{\sqrt m}\right)$$O(n\sqrt m)$$\text{bug}$$n$$[l_i,r_i]$$r_i$$r_i$$r_i$$[l_i,r_i,t_i]$$l_i$$r_i$$t_i$$[l,r]$$t$$[l,r]$$n$$m$$t_i$$O(n)$$O\left(\frac {n^3}{S^2}\right)$$O(S)$$O… text/html 2021-08-01T19:50:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E8%8E%AB%E9%98%9F%E7%AE%97%E6%B3%95_2&rev=1627818612&do=diff 莫队算法 2 树上莫队 算法模型 树上单点修改 $+$ 树上路径查询，且路径难以用树剖维护。 算法实现 考虑先将树转化为括号序列，设结点 $u$ 对应的左括号编号为 $\text{dfn}_{1u}$，右括号编号为 $\text{dfn}_{2u}$。 对当前维护的括号序列区间 $[l,r]$$[l,r]$$u\to v$$\text{dfn}_{1u}\le \text{dfn}_{1v}$$u$$v$$[\text{dfn}_{2u},\text{dfn}_{1v}]$$[\text{dfn}_{2u},\text{dfn}_{1v}] + \text{LCA}(u,v)$$m$$\{v_i\},\{w_i\}$$i$$c_i$$$ \sum_{i=1}^mv_i\sum_{j=1}^{c_i}w_j $$$O(1)$$O(1)$$O(n\sqrt m)$$S$$O(S)$$[l,r]$$r$$r+1$$O(n)$$r+1$$r+1$$O(S)$$O\left(ms+\frac {n^2}S\right)$$S=O\left(\frac n{\sqrt m}\right… text/html 2020-10-08T22:49:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E8%99%9A%E6%A0%91&rev=1602168557&do=diff 虚树 算法简介 一种用于加速树上 $\text{dp}$ 算法，时间复杂度 $O(k\log k)$，其中 $k$ 为树上的关键节点数。 算法思想 树上关键点数量较少时很多节点不需要进行 $\text{dp}$，考虑重建一棵树，只保留必要的节点。 发现所有关键节点的 $\text{LCA}$$\text{LCA}$$\text{dfs}$$\text{LCA}$$\text{LCA}$$p=\text{LCA}(u,v)$$u,v$$u,v$$p$$v$$\text{dfs}$$v$$v_2$$v_2$$p$$v_2$$v$$\text{LCA}(v_2,v)=p$$v$$v_2$$v_{k-1},v_k$$v_k=u$$\text{LCA}$$p$$p$$\text{dfs}$$p$$\text{dfs}$$p$$p$$p$$1$$q$$k_i$$\text{dp}$\begin{equation}v \text{ 是 }u \text{的儿子节点且} v \text{ 不是关键节点，}\text{dp}(u)\gets\min(\text{dp}(v),w(u,v))\e… text/html 2020-07-26T15:53:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E9%9D%99%E6%80%81%E7%82%B9%E5%88%86%E6%B2%BB&rev=1595750001&do=diff 静态点分治 算法简介 一种利用分治进行树上路径统计的算法，算法时间复杂度一般为 $O(n\log n)$。 算法思想 所有路径分为两种，一种是过根结点的，一种是完全在根结点的某棵子树中的。 因此可以考虑分治算法，选取一个点将无根树转换为有根树，然后递归处理每个棵以根节点的儿子为根的子树。$\frac n2$$\log n$$O(n)$$O(n\log n)$$\text{sz}$$\text{mson}(u)=\max\left(\max\left(\text{sz}\left(\text{son}\left(u\right)\right),\text{tot_sz}-\text{sz}\left(u\right)\right)\right)$$\text{mson}$$O(n)$$\text{tot_sz}$$n$$k$$k$$O(n^2)$$O(n)$$O(n\log n)$$\text{dist}$$k\le 10^7$$10^7$$\text{dist}$$\text{memset}$$\text{vector}$$q$$\text{mark}$$\text{dist… text/html 2020-10-08T15:16:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E9%87%8D%E6%9E%84%E6%A0%91&rev=1602141372&do=diff 重构树 算法简介 一种用于解决从任意询问点出发在边权或点权等限制下能到达的点集的信息维护问题的算法。 算法例题 例题一 洛谷p4197 题意 给定 $n$ 个点和 $m$ 条边，每个点给定一个点权，每条边给定一个边权。接下来 $q$$v$$x$$k$$\text{Kruskal}$$0$$x$$x$$\text{dfs}$$k$$O((n+q)\log n+m\log m)$$n$$m$$q$$S$$l$$E$$r$$\text{LCA}$$S$$l$$S$$l$$\text{dfs}$$\in [l_1,r_1]$$\text{dfs}$$\in [l_2,r_2]$$O(m+n\log n)$ text/html 2021-08-04T20:37:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E9%87%8D%E9%93%BE%E5%89%96%E5%88%86&rev=1628080673&do=diff 重链剖分 算法简介 一种动态维护树上路径、子树信息的算法，单次操作时间复杂度 $O\left(\log^2 n\right)$ 算法思想 重链剖分的关键是把树上修改问题转化为区间修改问题 为方便理解，先考虑点权树问题 使用 dfs 序可以把子树查询和修改问题转化区间修改问题，单次操作时间复杂度 $O\left(\log n\right)$$\log n$$O\left(\log^2 n\right)$$\text{LCA}$$n$$v$$n$$0$$m$$\text{LCA}$$n$$m$$a$$b$$a$$b$$c$$a$$b$ text/html 2020-07-27T22:54:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:%E9%95%BF%E9%93%BE%E5%89%96%E5%88%86&rev=1595861673&do=diff 长链剖分 算法简介 一种可以在线性时间复杂度维护子树中仅限深度有关的信息的算法，主要用于一些特殊的 $\text{dp}$ 算法思想 类似重链剖分，将儿子分为重儿子和轻儿子，重儿子组成的链构成长链$n$$x$$k$$\ge k$$x$$k$$y$$x$$y$$x$$y$$y$$x$$O\left(n\log n\right)$$2^k$$x$$x$$x$$\text{len}(x)$$\text{len}(x)$$x$$n$$O\left(n\right)$$x$$k$$h_k=\lfloor \log_2 k\rfloor$$tk=k-2^{h_k}$$x$$2^{h_k}$$y$$y$$\ge 2^{h_k}$$tk$$tk\lt 2^{h_k}$$x$$k$$y$$\text{len}(x)$$y$$y$$O\left(1\right)$$O\left(n\log n\right)-O\left(1\right)$$n$$(i,j,k)$$i,j,k$$\text{dp}$$O(1)$$u$$u$$x$$O\left(\text{len}\left(x\right)\ri… text/html 2020-07-30T15:29:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:cdq%E5%88%86%E6%B2%BB&rev=1596094143&do=diff CDQ 分治 算法简介 一种利用分治解决问题的算法思想，时间复杂度一般为 $O(n\log^2 n)$。 算法例题 点对统计 洛谷p3810 题意 三维空间中给定 $n$ 个点，编号为 $1 \sim n$。 定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。$f[0 \sim n-1]$$O(n\log n\log v)$$\text{CDQ}$$O(n\log^2 n)$$O(\log n)$$x,y$$a\ge b\iff a_x\ge b_x \land a_y\ge b_y$$O(n^2)$$\text{dp}$$+$$-1\lt$$0$$\times$$\text{dp}$$\text{CDQ}$$\text{dp}$$\text{CDQ}$$O(n\log^2 n)$$1\sim n$$m$$\text{CDQ}$$n$$m$$(x,y)$$(x,y)$$x$$y$$(u_t,u_x,u_y)$$v_t\lt u_t,v_x\le u_x,v_… text/html 2021-08-25T22:05:05+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:dp%E5%A5%97dp&rev=1629900305&do=diff $\text{dp}$ 套 $\text{dp}$ 算法简介 把 $\text{dp}$ 当作内层状态进行转移。 算法例题 例题一 HDU4899 题意 给定一个长度为 $n$ 的字符串 $S$。对 $i=0\sim n$，求有多少长度为 $m$ 的 $T$ 满足 $\text{LCS}(S,T)=i$。其中字符集为 $\text{ATGC}$。 题解 首先 $\text{LCS}$ 的经典算法，设 $\text{dp}(i,j)=\text{LCS}(T[1\sim i],S[1\sim j])$$$ \text{dp}(i,j) = \begin{cases} \text{dp}(i-1,j-1)+1, & T[i] = S[j] \\ \max(\text{dp}(i-1,j),\text{dp}(i,j-1)), & T[i]\neq S[j] \end{cases} $$$S$$\text{dp}(i,\ast)$$\text{dp}(i-1,\ast)$$T[i]$$\text{dp}(i,\ast)$$0\le \text{dp}(i,j)-\te… text/html 2021-08-13T21:52:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:ett&rev=1628862736&do=diff ETT 算法简介 ETT 是一种利用括号序列维护动态树子树信息的算法。 单括号序列(dfs 序) 2021牛客暑期多校训练营6 E 题意 给定一棵树，初始时只有一个颜色为 $c$ 的 $1$ 号结点，接下来 $m$ 个操作： * 对结点 $u$ 添加一个颜色为 $c$$n+1$$n$$u$$c$$u$$\text{hson}(u)$$\text{dfr}(u)$$n+1$$u$$\text{dfr}(n+1)\gets \text{dfr}(u)$$\text{dfr}(n+1)\gets \text{hson}(u)$$\text{hson}(u)$$n+1$$u$$[\text{pos}(u),\text{pos}(\text{dfr}(u)))$$2$$c$$[\text{pos}(u),\text{pos}(\text{dfr}(u)))$$\text{pos}(u)$$\text{pos}(u),\text{pos}(v)$$\text{pos}(u)$$\text{splay}$$\text{pos}(u)$$\text{pos}(u)$$O(\log n… text/html 2020-07-28T17:21:35+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:kd_tree&rev=1595928095&do=diff KD_Tree 算法简介 一种特殊的二叉树，主要用于多维空间关键数据的搜索。 空间复杂度 $O(n)$，单次插入时间复杂度 $O(\log n)$，查询时间复杂度 $O\left(k\sqrt[1-\frac 1k]n\right)$，其中 $k$ 表示空间维数。 算法实现 为方便理解，这里仅讲解 2D_Tree，高维 KD_Tree 可以类推。实际上高维 KD_Tree 时间复杂度难以承受，算法竞赛中通常只涉及 2D_Tree。$\text{algorithm}$$\text{nth_element}$$O(n)$$O(n\log n)$$n$$m$$(x,y)$$(x,y)$$\text{ans}$$\text{pos}$$\text{pos}$$(x,y)$$\text{ans}$$(x,y)$$\text{pos}$$d_1$$d_2$$d_i$$d_i\gt ans$$n$$k$$2k$$n$$1 \sim n$$q$$L \sim R$$L \sim R$$L$$R$$(L,R)$$\left(1\sim L,R\sim n\right)$$n$$1 \sim n… text/html 2021-07-11T16:30:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:lct&rev=1625992248&do=diff LCT 算法简介 LCT 是一种动态维护森林连通性、路径信息的数据结构，时间复杂度为 $O\left(n\log n\right)$。 算法思想 LCT 将树上路径分为实链和虚链，每个非叶结点仅向他的一个儿子结点连实边，其余儿子连虚边。$\text{access}(x)$$\text{access}(x)$$x$$\text{access}$$\text{makeroot}(x)$$\text{access}(x)$$\text{splay}(x)$$x$$x$$x$$\text{findroot}(x)$$x$$\text{access}(x)$$x$$\text{splay}(x)$$x$$n$$m$$x$$y$$x$$y$$x$$y$$x$$y$$x$$y$$x$$y$$x$$y$$n$$1$$q$$u$$v$$c$$u_1$$v_1$$u_2$$v_2$$u$$v$$c$$u$$v$$1$$m$$u$$u\to v$$u$$1$$u$$\text{dis}(u)$$2$$\text{dis}(u)+\text{dis}(v)-2\text{dis}(\text{lca}… text/html 2021-08-15T16:02:48+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:lgv%E5%BC%95%E7%90%86&rev=1629014568&do=diff LGV 引理 算法简介 一种统计有向无环图不相交路径集的算法。 算法原理 定义路径的权值 $w(P)$ 表示路径 $P$ 的所有边权之积。 定义 $e(u,v)$ 表示所有 $u\to v$ 的路径的权值之和，即 $e(u,v)=\sum_{P\in\{u\to v\}}w(P)$。 定义起点集合为 $A$，其中第 $i$$a_i$$B$$i$$b_i$$S(A,B)$$S(A,B)$$c$$n$$i$$a_i\to b_{p_i}$$P$$1\sim n$$N(c)$$c$$P$$w(c)$$c$$$ M=\begin{bmatrix} e(a_1,b_1)&e(a_1,b_2)&\cdots&e(a_1,b_n)\\ e(a_2,b_1)&e(a_2,b_2)&\cdots&e(a_2,b_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(a_n,b_1)&e(a_n,b_2)&\cdots&e(a_n,b_n)\\ \end{bmatrix} $$$$ \det M=\sum_{c\in S(a,b)}(-1)^{N(c)}w(c) $$$1$… text/html 2020-08-16T15:17:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:prufer%E5%BA%8F%E5%88%97&rev=1597562254&do=diff Prufer 序列 算法简介 一种带编号生成树与数列之间的双射，主要用于解决组合计数问题。 Prufer 序列的性质 对一棵 $n$ 个结点的带标号树，考虑每次取编号最小的叶子结点，将其删除。 然后将与其相邻的结点加入 $\text{Prufer}$$n$$\text{Prufer}$$\text{Prufer}$$n-2$$n-2$$1\sim n$$n$$n-2$$1\sim n$$\text{Cayley}$$K_n$$n^{n-2}$$\text{Prufer}$$\text{Prufer}$$O(n\log n)$$\text{Prufer}$$n$$n$$O(n)$$\text{Prufer}$$\text{Prufer}$$n$$m$$k$$s_i$$d_i$$\text{Prufer}$$\cfrac{(k-2)!}{\prod_{i=1}^k(d_i-1)!}$$\prod_{i=1}^k s_i^{d_i}$$c_i=d_i-1$$$\sum_{\sum d_i=2k-2}\cfrac{(k-2)!\prod_{i=1}^k s_i^{d_i}}{\pro… text/html 2021-08-27T17:34:01+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:slope_trick&rev=1630056841&do=diff slope trick 算法简介 一种维护凸包的技巧。 算法实现 假定一个函数 $f(x)$ 是连续函数，可以被划分为多条直线，直线的斜率单调递增/递减，则可以用最终直线 $g(x)$ 和可重集 $S$ 来表示 $f(x)$。 例如 $f(x)=|x-1|$ 可以表示为 $(x-1,\{1,1\})$$f(x)=|2x-4|+|3x|$$(5x-4,\{0,0,0,0,0,0,2,2,2,2\})$$f(x)=(k_1x+b_1,S_1),g(x)=(k_2x+b_2,S_2)$$f(x),g(x)$$$ f(x)+g(x)=((k_1+k_2)x+b_1+b_2,S1\cup S_2) $$$A$$i$$a_i\gets a_i+1$$a_i\gets a_i-1$$a_i\gets a_i-i$$f_i(x)$$a[1\sim i]$$a_i\le x$$g_i(x)$$a[1\sim i]$$a_i=x$$g_i(x)=f_{i-1}(x)+|x-a_i|$$f_i,f_{i-1}$$0$$g_i$$1$$f_i$$g_i$$S$$g_i$$S$$k$$g_i$$$ f… text/html 2021-08-24T17:22:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:wqs%E4%BA%8C%E5%88%86&rev=1629796954&do=diff wqs二分 一种用于解决恰好选 $a$ 个物品的最优方案的算法。 其中设 $F(x)$ 表示 $a=x$ 的最佳收益函数，则 $F(x)$ 必须是凸函数。 算法实现 由于 $F(x)$ 为凸函数，所以对固定的斜率 $k$ 求出斜线与 $F(x)$ 构成的凸包的切点，当斜率单调变化时切点位置也是单调变化的。$x=a$$k$$x$$F(x)$$y=kx+b$$b=y-kx$$k$$b$$x$$y=b+kx$$a$$F(x)$$x$$F(x)$$k$$k$$+ka$$O\left(m\log m\log V\right)$$k$$F(x)$$x$$F(x)$$V$$-nV$$\text{wqs}$$\text{dp}$$n$$a$$b$$i$$p_i$$q_i$$p_i+q_i-p_iq_i$$F(x,y)$$x$$y$$x$$F(x,y)$$\text{wqs}$$O(n\log v)$$F(x,b)$$F(x,b)$$\text{wqs}$$O\left(n\log^2 v\right)$$F(a,b)$$A$$A[l\sim r]$$(\sum_{i=l}^r a_i+1)^2…