毛估估就行

idea, solution, std, data from he_____he

这道题送了很多分，但非常抱歉没有成功卡掉 $O\left(\frac{n^3}{w}\right)$ 等高复杂度的乱搞做法，在这里向大家谢罪。

算法一

我会 floyd！时间复杂度 $O(n^3)$，可以通过子任务 1，期望得分 $10$ 分。

算法二

我会每次 $O\left(\frac{n^2}{w}\right)$ bfs！时间复杂度 $O\left(\frac{n^3}{w}\right)$，可以通过子任务 1、2，期望得分 $30$ 分。

算法三

如果每条边以 $\frac{1}{2}$ 概率出现，那么可以认为两点之间几乎一定距离不超过 $2$，输出 $1$ 即可。

结合算法 2，可以通过前 3 个子任务，期望得分 $50$。到目前为止这些分都是送给大家的！

算法四

选择一个点 $v$，bfs 算出 $v$ 到其他点的距离。那么如果对于两个点 $x,y$，最短路经过了 $v$ 或 $v$ 的邻域，那么就可以用 $d_x+d_y$ 来近似该最短路长度，其中 $d_x,d_y$ 分别为 $v$ 到 $x,y$ 的距离。容易发现这一定不超过精确答案 $+2$，将其 $-1$ 即可。

那么我们可以每次选择度数最大的点作为 $v$，然后删除 $v$ 及其邻域。一直操作直到所有点都被删除，每次查询时求出 $\min\limits_{v} (d_x+d_y)$ 即可。我们来证明这些 bfs 的复杂度总和不超过 $O(n^2)$。

每次 bfs 的复杂度为 $O(n+m)$，其中 $m$ 为 bfs 时的边数。由于选择的点 $v$ 为度数最大的一个点，有 $\mathrm{deg}(v)\geq \frac{2m}{n}$。设每一次删除时边数分别为 $m_1,m_2,\ldots,m_s$，由于最多删除 $|V|$ 个点，有

$$\sum\limits_{i=1}^s \frac{2m_i}{n}\leq n$$

所以时间复杂度不超过

$$O\left(n^2+\sum\limits_{i=1}^s m_i\right)= O(n^2)$$

那么总复杂度即为 $O(n^2+qn)$，可以通过前 4 个子任务，期望得分 $70$ 分。

算法五

由于 $q$ 过大，并且查询复杂度为删除次数，考虑缩小删除次数。设只选 $B$ 个 $v$ 删除。设剩余的图为 $G'=(V',E')$。现在只需支付 $O(qB)$ 的代价后估计出 $G'$ 中两两的距离即可。

注意到，由于每次删除时 $v$ 的度数单调不增，所以剩余的点度数均不超过 $\frac{n}{B}$，这意味着 $|E'|\leq O\left(\frac{n^2}{B}\right)$。那么简单从所有点开始 bfs 即能做到 $O\left(\frac{n^3}{B}\right)$ 的时间复杂度。

总时间复杂度为 $O\left(\frac{n^3}{B}+qB\right)$ 。取 $B=\Theta\left(n^{\frac 32}q^{-\frac 12}\right)$ 即可做到 $O(n^{\frac 32}q^\frac 12)$ 的时间复杂度。由于常数非常小，可以通过所有子任务，期望得分 $100$ 分。

算法六

实际上，本题能够做到 $O\left(n^\frac 53 q^\frac 13\right)$ 的复杂度，但由于篇幅所限，在这里就不展开了。有兴趣的同学可以等待集训队论文公开后阅读本人的集训队论文。

这也带来了一个 $O\left(n^\frac 73\right)$ 复杂度的，以绝对值最多差 $1$ 的方式估计两两最短路的算法。目前学术界最优的算法为 $\tilde O\left(n^\frac 73\right)$ 的算法，我们在这里把复杂度中的 $\mathrm{polylog}$ 因子去掉了。并且此做法易于实现，而且有着不错的常数表现。

理论复杂度

idea, solution from x_Yi_x, std, data from hehezhou

算法一

我会暴力！

dp 计算出把 $1\ldots n$ 划分成 $r$ 个数，最小的数为 $x$ 的方案数。

再 dp 计算出把 $1\ldots n$ 划分成若干数，最大的数不超过 $x$ 的方案数。

最后暴力枚举 $r$ 号点的取值，合并三部分即可。

复杂度 $O(n^2r+n^2+n^4)$，可以通过子任务 1，期望得分 $10$ 分。

算法二

使用 FFT 优化最后合并过程，复杂度可降为 $O(n^2r+n^2\log n)$，常数不大可以通过子任务 2，期望得分 $30$ 分。

算法三

设答案的生成函数为 $G_r(x)=\sum a_{n,r}x^n$，其中 $a_{n,r}$ 表示这组 $n,r$ 的答案。

再设 $F_r=\frac{G_r}{\prod_{i=1}^{r-1}\frac{1}{1-x^i}}=G_r\prod_{i=1}^{r-1} (1-x^i)$。

那么 $F_r$ 的组合意义即为要求 $1\ldots r$ 号点填的数必须相同，填数的方案数。

显然有 $F_r(x)=\sum_{i=0}x^{ri}(\prod_{j=1}^i\frac{1}{1-x^j})^2$。

可以直接计算做到 $O(n^2\log n)$ 或 $O(n^2)$，可以通过子任务 2，期望得分 $30$ 分。

算法四

考虑 $r=1$ 的情况。

以下均在计算 $F_r$ 的求法，从 $F_r$ 变为 $G_r$ 是简单的，并且以下均把填数方案记为：

$$\left[c\ldots c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right]$$

考虑如下映射：

$$\left[c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right]\mapsto \begin{bmatrix}c&a_1&\ldots\\b_1&b_2&\ldots\end{bmatrix}$$

这是一个单射但不满。没有原像的元素形如 $\begin{bmatrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{bmatrix}(a_1< b_1)$。

我们将这些元素重写为 $\left[b_1\quad\begin{matrix}a_1&a_2&\ldots\\b_2&b_3&\ldots\end{matrix}\right](b_1>a_1)$。

再次构造映射：

$$\left[c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right](c>a_1)\mapsto \begin{bmatrix}c-1&a_1&\ldots\\b_1&b_2&\ldots\end{bmatrix}$$

这次没有原像的元素形如 $\begin{bmatrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{bmatrix}(a_1+1< b_1)$，将它写为 $\left[b_1\quad\begin{matrix}a_1+1&a_2&\ldots\\b_2&b_3&\ldots\end{matrix}\right](b_1>a_1+1>a_2)$。

再再次构造映射：

$$\left[c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right](c>a_1>a_2)\mapsto \begin{bmatrix}c-2&a_1-1&\ldots\\b_1&b_2&\ldots\end{bmatrix}$$

之后的流程是类似的，不断递归，我们便可以得到 $r=1$ 时的 OGF：

$$(\sum_{i=0}(-1)^ix^{i(i+1)/2})P^2(x)$$

其中 $P(x)$ 是划分数的 OGF。

时间复杂度 $O(n\log n)$，可以通过子任务 3，结合之前算法期望得分 $40$ 分。

算法五

再考虑 $r=2$ 怎么做。

依然是构造映射：

$$\left[c~~c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right]\mapsto \begin{bmatrix}c&a_1&\ldots\\c&b_1&\ldots\end{bmatrix}$$

没有原像的元素为：$2\times \begin{bmatrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{bmatrix} (a_1< b_1)$。这在算法四中已经介绍过如何计算。

时间复杂度 $O(n\log n)$，可以通过子任务 4，结合之前算法期望得分 $70$ 分。

算法六

考虑扩展到任意 $r$。

记对于某个 $r$，答案关于 $n$ 的 OGF 为 $F_r(x)$。

同样的，我们构造映射：

$$\left[\ldots~~c~~c~~c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right]\mapsto \left[\ldots~~c\quad\begin{matrix}c&a_1&\ldots\\c&b_1&\ldots\end{matrix}\right]$$

没有原像的元素有两种：

1. $\left[\ldots~~c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right](c>a_1,c>b_1)$，这种的贡献为 $x^{r-2}F_{r-2}(x)$。
2. $2\times \left[\ldots~~c\quad\begin{matrix}a_1&a_2&\ldots\\b_1&b_2&\ldots\end{matrix}\right](c=a_1,c>b_1)$，这种的贡献为 $2F_{r-1}(x)-2F_r(x)$。

于是我们有 $$F_r(x)+x^{r-2}F_{r-2}(x)+2F_{r-1}(x)-2F_r(x)=F_{r-2}(x)$$ ，即 $$F_r(x)=2F_{r-1}(x)+(x^{r-2}-1)F_{r-2}(x)$$

递推求出 $F_r(x)=AF_1(x)+BF_2(x)$ 即可。

时间复杂度 $O(n\log n+r^3)$，可以通过此题，期望得分 $100$ 分。

算法七

(by ElegiaInferno)

问题的关键为计算 $$ \sum_{k\ge 0} \frac{x^{kr}}{(1-x)^2(1-x^2)^2\cdots (1-x^k)^2} $$ 设 $\phi(x) = \prod_{k\ge 1} (1-x^k)$，提出 $\phi(x)^{-2}$，考虑计算 $$ F =\sum_{k\ge 0} x^{kr} (1-x^{k+1})^2(1-x^{k+2})^2\cdots $$ 由基本的 $q$-推导，我们有 $$ (1-qx)(1-qx^2)\cdots = \sum_{k\ge 0} \frac{x^{k(k+1)/2}}{(1-x)\cdots (1-x^k)} (-q)^k $$ 因此，带入 $q=x^k$ 有 $$ \begin{aligned} F & = \sum_{k\ge 0} x^{kr} \left( \sum_{j\ge 0} \frac{x^{j(j+1)/2}}{(1-x)\cdots(1-x^j)} (-1)^j x^{jk} \right)^2\\ &= \sum_{j_1 \ge 0} \sum_{j_2\ge 0} \frac{x^{(-1)^{j_1}j_1(j_1+1)/2}}{(1-x)\cdots(1-x^{j_1})} \cdot \frac{(-1)^{j_2}x^{j_2(j_2+1)/2}}{(1-x)\cdots(1-x^{j_2})} \cdot \frac 1{1-x^{j_1+j_2+r}}\\ &= \sum_{k\ge 0} \frac 1{1-x^{k+r}} \cdot [q^k] (1-qx)^2(1-qx^2)^2 \cdots \end{aligned} $$ 设 $F(q,x) = \prod_{k\ge 1} (1-qx)^2$，对等式 $F(qx,x)(1-xq)^2 = F(q,x)$ 提取系数，设 $f_n = [q^n]F$，得到 $$ f_n = \frac{x^n}{1-x^n}(f_{n-2}-2f_{n-1}) $$ 由于 $f_n$ 的最低次项是 $\Theta(n^2)$ 量级，求和有贡献的项数是 $\Theta(\sqrt N)$ 的。暴力计算的复杂度为 $O(N^{3/2})$，如许使用 FFT，可以分治维护矩阵链乘，复杂度为 $\tilde O(N + r N^{1/2})$。

bonus：

算法三实际上可以是 $O(\frac{n^2\log n}{r})$。与算法七拼接可以做到 $\tilde O(n^{1.25})$，但是能不能做到 $\tilde O(n)$ 呢。

广为人知题

idea, solution, std, data from djq_cpp

这道题很晚才出好，数据不强还出了锅，std 常数起飞，在这里向大家谢罪。

算法一

我会对每次修改和查询暴力枚举所有子串！时间复杂度 $O(n^2(m+q))$，实现良好可以通过子任务 1，期望得分 $[0, 10]$ 分。

算法二

用二维前缀和 + KMP 优化算法一，时间复杂度 $O(n^2 + nm + q)$，期望得分 $10$ 分。

算法三

考虑子任务 $3$。

取阈值 $B > 2 \log n + \log \frac{1}{\epsilon}$，则所有长为 $B$ 的子串两两不同的概率至少为 $1 - \epsilon$。因此，我们可以用 KMP + 前缀和维护长度小于等于 $B$ 的模式串，再用二维数点解决长度大于 $B$ 的模式串。时间复杂度 $O((n + m + q) \log n)$，期望得分 $20$ 分。

算法四

考虑莫队。左端点变化对答案的影响可以在正串后缀树上统计，右端点变化的影响则可以在反串后缀树上统计。瓶颈是子串定位和线段上数点。

复杂度 $O((n\sqrt{q} + m) \log n)$，二次离线后可能可以做到 $O((n + m + q) \sqrt{n})$，期望得分 $35$ 分。

算法五

对 $S$ 建立后缀自动机和 parent tree，并将后缀自动机重链剖分。

这里，对每个自动机结点 $v$，记以 $v$ 为起点的路径有 $f_v$ 条，以 $v$ 为终点的有 $g_v$ 条。则令 $(u, v)$ 为重边当且仅当 $2f_v > f_u$ 且 $2g_u > g_v$。则可以发现一条路径上至多经过 $O(\log n)$ 条轻边。

对于$S$ 的子串 $T$，$T$ 的后缀中模式串的个数是由 $T$ 在 SAM 上对应的结点 $v$ 以及 $v$ 所对应的模式串决定的。进一步地，只需将 $v$ 到根的路径上模式串个数 $a_v$ 减去 $v$ 上长度比 $|T|$ 大的模式串个数即可。

对于每次查询，可以把子串定位到自动机的路径上，并计算路径上每个结点的贡献之和。

考虑路径定位：对原串和 DAG 重链预处理 $O(n \log n) - O(1)$ 子串 LCP 可以做到 $O(q \log n)$。

考虑答案统计：对于第一种贡献，对 DAG 重链记 $a_v$ 的前缀和即可；对于第二种贡献，可以将问题转化成每条重链上的斜 45 度平行四边形数点，在坐标变换后即是普通的二维数点。

总复杂度为 $O((n + m) \log n + q \log^2 n)$，期望得分 $100$ 分。

使用类似全局平衡二叉树的带权线段树技巧还可以将理论复杂度优化至 $O((n + m + q) \log n)$，但可能不 practical。