FUN WORLD

拉格朗日插值 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi​,yi​)，求出过这 nnn 个点的 n−1n-1n−1 次多项式 L(x)L(x)L(x)。 拉格朗日插值多项式： L(x)=∑i=0n∏j≠i(x−xj)∏j≠i(xi−xj)⋅yiL(x)=\sum_{i=0}^n\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}\cdot y_i L(x)=i=0∑n​∏j=i​(xi​−xj​)∏j=i​(x−xj​)​⋅yi​ 时间复杂度 O(n2)O(n^2)O(n2)。 快速傅里叶变换 FFT 单位根 定义：ωn=e2πin=cos⁡(2πn)+i⋅sin⁡(2πn)\omega_n=e^{\frac{2\pi i}n}=\cos(\frac{2\pi}n)+i\cdot\sin(\frac{2\pi}n)ωn​=en2πi​=cos(n2π​)+i⋅sin(n2π​)。 两个复数相乘，模长相乘，幅角相加。 性质： ω2nn+k=−ω2nk\omega_{2n}^{n+k}=-\omeg ...

Statement 给出 nnn 个模板串 SiS_iSi​，求合法字符串个数，满足：可以被划分成非空的两段，使得其中每一段都是一个模板串的前缀。 数据范围：n≤104n\le10^4n≤104，∣Si∣≤30|S_i|\le30∣Si​∣≤30，∣Σ∣≤26|\Sigma|\le26∣Σ∣≤26。 Solution 如果看过网上的一些题解觉得没懂，那么你可以考虑看看这篇题解。 考虑用字符串总数减去重复字符串个数。对模板串建立 Trie，全集为 Trie 树节点数（不含根节点）的平方。 重复字符串形如：1 2 3∣41 2∣3 41∣2 3 4\begin{aligned}1~2~3|4\\1~2|3~4\\1|2~3~4\end{aligned}1 2 3∣41 2∣3 41∣2 3 4​，其中每个数字表示一段字符串。这个字符串在枚举 444、3 43~43 4 和 2 3 42~3~42 3 4 时都会被枚举到。 可以发现 AC 自动机上 3 43~43 4 的 fail 正好指向 444，2 3 42~3~42 3 4 的 fail 正好指向 3 43~43 4；所以考虑在 ...

Statement 给定字符串 sss，定义前缀 iii 表示 s[1:i]s[1:i]s[1:i]。mmm 次询问，每次询问给出两个数 l,rl,rl,r，求从前缀 l∼rl\sim rl∼r 中选出两个前缀的所有方案中，这两个前缀的最长公共后缀长度的最大值。 数据范围：∣s∣≤105|s|\le10^5∣s∣≤105，∣Σ∣≤2|\Sigma|\le2∣Σ∣≤2。 Solution 题目可以转化为后缀树上点集 SSS 中选两个点的 LCA 的 maxlen\text{maxlen}maxlen 最大值，即 max⁡i∈S,j∈S,i≠j{maxlen(LCA(i,j))}\max\limits_{i\in S,j\in S,i\ne j}\{\text{maxlen}(\text{LCA}(i,j))\}i∈S,j∈S,i=jmax​{maxlen(LCA(i,j))}。这就变成了一个纯树上数据结构问题。 离线询问，将询问按 rrr 排序。需要支持的操作是加入一个点，求后缀 max⁡\maxmax。可以看出我们打算在每个 iii 处维护所有 (i,j)(i,j)(i,j) ...

Statement 给定整数 n,an,an,a。 定义『好的珠子』由一个无序三元组 (x1,x2,x3)(x_1,x_2,x_3)(x1​,x2​,x3​) 表示，且满足 1≤xi≤a1\le x_i\le a1≤xi​≤a，gcd⁡{x1,x2,x3}=1\gcd\{x_1,x_2,x_3\}=1gcd{x1​,x2​,x3​}=1。 定义『好的项链』是一串由 nnn 个珠子构成的环，满足相邻两个珠子不同。 试统计本质不同（即循环不同构）的好的项链的个数，答案对 109+710^9+7109+7 取模。 TTT 组数据。数据范围：n≤1014n\le10^{14}n≤1014，a≤107a\le10^7a≤107，T≤10T\le10T≤10。时限 3 s3~\text{s}3 s。 Solution 二合一题。 统计好的珠子个数 考虑容斥。设 f(x)f(x)f(x) 表示 gcd=x\text{gcd}=xgcd=x 的无序三元组个数，g(x)g(x)g(x) 表示 gcd⁡\gcdgcd 为 xxx 的倍数的无序三元组个数。 显然有 g(d)=∑d∣nf(x)g(d) ...

Statement 给定长度为 nnn 的序列 aia_iai​，qqq 次询问，每次询问给定 l,rl,rl,r，求 a[l:r]a[l:r]a[l:r] 的所有非空子串的最小值之和。 数据范围：n,q≤105n,q\le10^5n,q≤105，∣ai∣≤109|a_i|\le10^9∣ai​∣≤109。 Solution 一个询问 l,rl,rl,r 的答案 ans(l,r)=ans(l,x−1)+ans(x+1,r)+ax⋅(x−l+1)⋅(r−x+1)\text{ans}(l,r)=\text{ans}(l,x-1)+\text{ans}(x+1,r)+a_x\cdot(x-l+1)\cdot(r-x+1)ans(l,r)=ans(l,x−1)+ans(x+1,r)+ax​⋅(x−l+1)⋅(r−x+1)。其中 xxx 是 l,rl,rl,r 中最小值元素的下标。 ans(l,x−1)\text{ans}(l,x-1)ans(l,x−1) 和 ans(x+1,r)\text{ans}(x+1,r)ans(x+1,r) 本质相同，现考虑求后者。 如果记 fi=[1,i]+[ ...

Statement 给出一个长度为 nnn 的排列 PPP，以及 mmm 个询问。每次询问某个区间 [l,r][l,r][l,r] 中，最长的值域连续段长度。 数据范围：n,m≤5×104n,m\le5\times10^4n,m≤5×104。 Solution 考虑莫队区间如何扩展。 维护每个元素向上延伸和向下延伸的最大距离。加入新元素 xxx 时，会合并 x−1x-1x−1 所在集合和 x+1x+1x+1 所在集合；但是对答案有贡献的只可能是合并后集合的端点。所以可以只更新这两个元素，也方便了撤销。 时间复杂度 O(nm)O(n\sqrt m)O(nm​)。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>const int N = 5e4 + 3, SN = 293;int n, q, a[N], B, T, ans[N];#define ...

Statement 给一个树，nnn 个点，有点权，初始根是 111。mmm 个操作，种类如下： 1 x\texttt{1}~x1 x：将树根换为 xxx。 2 x y\texttt{2}~x~y2 x y：给出两个点 x,yx,yx,y，从 xxx 的子树中选每一个点，yyy 的子树中选每一个点，求点权相等的情况数。 数据范围：1≤n≤1051\le n\le10^51≤n≤105，1≤m≤5×1051\le m\le5\times10^51≤m≤5×105 , 1≤ai≤1091\le a_i\le10^91≤ai​≤109。 Solution 根号做法，按颜色的出现次数根号分治。 对于出现次数 >n>\sqrt n>n​ 的颜色 最多 n\sqrt nn​ 种颜色，那么对于每种颜色 O(n)O(n)O(n) 地统计 xxx 子树内出现次数 cntx\text{cnt}_xcntx​。询问 x,yx,yx,y 的答案就是 cntx⋅cnty\text{cnt}_x\cdot\text{cnt}_ycntx​⋅cnty​。 当然由于换根，可能 xxx 的 ...

排序算法 平均 最好 最坏 辅助空间 稳定性 概述 冒泡排序 O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(n2)O(n^2)O(n2) T(1)T(1)T(1) 稳定 扫一遍移动当前已知最大元素与下一元素交换 简单选择排序 O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) O(n2)O(n^2)O(n2) T(1)T(1)T(1) 不稳定 第 iii 次选择剩余最大值与第 iii 个元素换位 插入排序 O(n2)O(n^2)O(n2) O(n)O(n)O(n) O(n2)O(n^2)O(n2) T(1)T(1)T(1) 稳定 拿出当前元素，挨个尝试往前放置找到合适位置 希尔排序 O(n)O(n)O(n) T(1)T(1)T(1) 不稳定 步长从 n2\frac{n}{2}2n​ 到 111 进行直接插入排序 归并排序 O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) O(nlog⁡n)O(n\log n)O(nlogn) T(n)T(n)T(n) 稳 ...

并查集 设 mmm 为合并次数，nnn 为点数，则： 朴素：O(mn)O(mn)O(mn) 按 size / height 合并：O(mlog⁡n)O(m\log n)O(mlogn) 路径压缩：O(mlog⁡n)O(m\log n)O(mlogn) 按 size / height 合并 + 路径压缩：近似 O(m)O(m)O(m) 最小生成树 MST Boruvka 每一轮，对每个联通块选择一条到其他联通块的一条最短路径。 时间复杂度 O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)。 最近公共祖先 LCA 倍增 & 树剖 时间复杂度 O((n+q)log⁡n)O((n+q)\log n)O((n+q)logn)。 Tarjan 只能离线。 时间复杂度 O(n+q)O(n+q)O(n+q)。 欧拉序 + ST 表 时间复杂度 O(nlog⁡n+q)O(n\log n+q)O(nlogn+q)，但是有 222 倍常数，实际也不会很快。 DFS 序 + ST 表 讨论一组询问 u,vu,vu,v 和他们的 lca\text{l ...

树状数组 一维：区间修改 区间查询 设原序列 {ai}\{a_i\}{ai​} 的差分序列为 {di}\{d_i\}{di​}（即 di={ai−ai−1i≥2a1i=1d_i=\begin{cases}a_i-a_{i-1}&i\ge2\\a_1&i=1\end{cases}di​={ai​−ai−1​a1​​i≥2i=1​）。 ∑i=1nai=∑i=1n∑j=1idj=∑i=1ndi×(n−i+1)=(n+1)×∑i=1ndi −∑i=1ni×di\begin{aligned} \sum\limits_{i=1}^na_i&=\sum_{i=1}^n\sum_{j=1}^id_j\\ &=\sum_{i=1}^nd_i\times(n-i+1)\\ &=(n+1)\times\sum_{i=1}^nd_i~-\sum_{i=1}^ni\times d_i \end{aligned} i=1∑n​ai​​=i=1∑n​j=1∑i​dj​=i=1∑n​di​×(n−i+1)=(n+1)×i=1∑n​di​ −i=1∑n​i×di​​ 因此，除 ...