枪打出头鸟

idea, solution, std, data from 127

​ 没有啥特别的，考虑我们想要二分的话怎么办，那我们就要检查 $x$ 是否出现在一个前缀中

​ 注意到线性空间的交还是线性空间，并且我们有线性基交的算法

​ 那么求交，直接二分是 $O(q\log n\log V)$ 的

​ 发现只会变小 $\log V$ 次，在这个基础上二分是 $O(q\log V\log\log V)$ 的

​ 既然后面的线性空间是前面的线性空间的子空间，那么我们只要按照基的元素出现顺序造一个新的基

​ 然后看把 $x$ 表出来基最小的不出现的时间，就是答案

伟大 NIT 的贸易计划

idea, solution, std, data from 127

​ 首先我们考虑暴力$DP$，等价的说，我们考虑一个矩阵 $M_{i,j}=[i+K\geqslant j]$，答案就是 $tr(M^n)$

​ 熟知，$tr(M^n)=\sum \lambda_i^n$

​ 由牛顿恒等式或者由幂和的推导，不妨设矩阵的特征多项式为 $F$，则 $tr(M^n)=[x^n]\frac{(F')^R}{F^R}$，其中 $F^R$ 表示将 $F$ 翻转

​ 由特征多项式与行列式的关系我们可知，$F$ 的第 $\partial_0 F-k$ 项（倒数第 $k$ 项，倒数第 $0$ 项即最高项）就是矩阵的 $k$ 阶主子式之和（若 $k=0$，则为 $1$）乘上 $(-1)^k$

​ 那么现在问题转化为求 $k$ 阶主子式之和，即从主对角线上选出来 $k$ 个位置，这 $k$ 行 $k$ 列形成的矩阵的行列式

​ 首先注意到这个矩阵的下三角总是满的，并且若新的矩阵中格子 $(i,j)$ 为 $1$，则 $(i+1,j),(i,j-1)$ 都为 $1$（左边和下面）

​ 那么这个矩阵的行列式非 $1$ 即 $0$，当且仅当这个矩阵为下三角矩阵时行列式值为 $1$（鸽巢证一下）

​ 我们可以将矩阵从左上到右下沿主对角线分为 $\lceil \frac{m}{K}\rceil$ 份，每份是一个 $K\times K$ 的矩阵，最后一个矩阵可能不足 $K$ 阶

​ 那么我们发现同一个矩阵中只会选取一行一列，若相邻两个矩阵都选取了行列，则后一个元素在其矩阵中的相对位置要靠后

​ 其实就是选择恰 $k$ 个 $[1,m]$ 的数使得 $a_{i+1}>a_i+K$（与容斥殊途同归），那么插空法即可，多项式的系数就是一个组合数

​ 然后后面的 $\frac{(F')^R}{F^R}$ 是线性递推，就做完了

​ 时间复杂度是 $O(\min(n,\frac{m}{K})\log n\log \min(n,\frac{m}{K}))$（之前出题人非常蠢，花了三只 $\log$ 求了个组合数）

可爱多的字符串

idea, solution, std, data from sslz_fsy

算法 1

我会暴力 $kmp$！期望得分 5 分。

算法 2

解决 $r=n,w_i=1$ 的情况。

设 $pt_i$ 表示 $S[i,n]$ 在后缀树上的点。 我们考虑将题目要求的每个点的深度之和变成求每个点的子树大小之和。

考察 $next$ 树的性质，若 $S[l,x]$ 是 $S[l,y](y\ge x)$ 的 $border$ ，则 $y$ 将出现在 $x$ 的子树中，$y$ 也唯一对应了 $S[l,x]$ 在 $S[l,n]$ 中的一个出现位置（即 $S[y-x+l,y]$），故一个节点 $x$ 的子树大小即为串 $S[l,x]$ 在 $S[l,n]$ 中的出现次数。

现在要统计 $S[l,n]$ 的每个前缀在 $S[l,n]$ 中的出现次数， 我们从后向前建立后缀自动机，那么答案即为后缀树上 $pt_l$ 到根的每一个点的 $(len_i-len_{fa_i})\times |Right_i|$。

使用 $LCT$ 维护，时间复杂度 $O(n\log n)$。结合算法 1，期望得分 $15$ 分。

算法 3

解决数据随机，$w_i=1$ 的情况。

考虑延续算法2，我们要求出 $S[l,r]$ 的每个前缀在 $S[l,r]$ 中的出现次数，找到 $S[l,r]$ 在后缀树上对应的点 $x$。对于 $x$ 到根路径上的每一个点 $y$，枚举一个长度 $len'\in [len_{fa_y}+1,len_y]$，那么就在其子树查询 $[l,r-len'+1]$ 的点数。

使用线段树合并。对于数据随机的情况，$len'$ 的期望为 $\log n$，故时间复杂度为 $O(n\log^2n)$，结合算法 2，期望得分 $25$ 分。

算法 4

解决数据随机的情况。

考虑和算法 3 的不同之处，即若 $S[j,k]=S[l,l+k-j]$，则有 $w_k$ 的贡献。同样枚举一个 $len'$，那么即查询其子树中的 $\sum_{i=l+1}^{r-len'+1}w_{i+len'-1}$。

对正序串对称建立后缀自动机，设当前点代表的后缀为 $p$，找到 $[p,p+len'-1]$ 在对称的树上对应的点，可以将问题转换为子树查询。

复杂度 $O(n\log^2 n)$，结合算法 2 期望得分 $35$ 分。

算法 5

解决 $r=n$ 的情况。

优化算法 $2$，对于 $S[j,k]=S[l,l+k-j]$，有 $w_{k}$ 的贡献，枚举 $j$，求出 $w$ 的前缀和 $S$，相当于有 $S_{j+lcp(l,j)-1}-S_{j-1}$ 的贡献。

下面考虑求 $\sum_{j=l+1}^nS_{j+lcp(l,j)-1}$。考虑树链剖分，设 $pt_j$ 表示后缀 $j$ 代表的点，对于 $pt_j$ 的祖先和一条重链的交的最深的点 $x$，对于 $x$ 的重儿子的子树，要求 $\sum_{j>l}S_{j+len_x-1}$，使用算法 4 对称后缀树的做法即可。

剩下的情况，使用 $dsu~on~tree$，考虑这个重链的前缀对 $x$ 上询问的影响，按链从上到下的顺序扫描线，扫到一个点就将其轻子树中的 $j$ 暴力加入树状数组。记每个 $j$ 在重链上对应的 $len_x$ 为 $len'_j$，此时有 $lcp(l,j)=len'_j$。那么我们查询 $>l$ 的 $j$ 的 $S_{j+len’_j-1}$ 之和就可以了。

最后，要减去 $pt_l$ 自己的那个轻子树的贡献，处理方法同上，仍然使用对称的后缀树做子树查询。

复杂度 $O(n\log^2 n)$。结合算法 $4$ 期望得分 $55$ 分。

算法 6

解决 $w_i=1$ 的情况。

继续算法 $5$，我们知道要求的式子就是 $\sum_{j=l}^r \min(lcp(l,j),r-j+1)$。

此时问题变成了 CF1098F，没有想到这道题竟然有 $next$ 树深度和这样的组合意义。

使用 CF1098F 的做法，这里不再赘述。结合算法 4，期望得分 $60$ 分。

算法 7

解决 $n,m\le 10^5$ 的情况。

改进算法 5，设 $w$ 的前缀和为 $S$，将要求的式子写为 $\sum_{j\in(l,r]} S_{\min(lcp(l,j)+j-1,r)}$。

同样使用 $dsu~on~tree$，设 $pt_l$ 与重链的交为 $x$，那么要求 $j$ 与重链的交在 $x$ 的上方，求 $S_r\times \sum_{j\in (l,r]} [len'_j+j-1\ge r]+\sum_{j\in (l,r]}[len'_j+j-1< r]S_{len'_j+j-1}$。

使用从上至下的顺序扫描线，对于 $x$ 处的查询，是一个矩阵数点问题，使用树套树，复杂度 $O(n\log^3 n)$。

对于 $O(\log n)$ 次子树询问 $\sum_{j\in (l,r]}S_{\min(j+len_x-1,r)}$，同样使用对称后缀树的思想进行子树查询。期望得分 $80$ 分。

算法 8

idea from mayaohua

想一想怎么优化算法 7。我们发现算法 7 中要求 $j$ 与重链的交在 $x$ 上方十分多余。

我们转而将式子写成 $\sum_{j\in (l,r]} S_{min(r,j+len'_j-1,j+len'_l-1)}$，要求 $j$ 在重链的轻子树中（除 $pt_l$ 之外的就可以，这个可以通过对称后缀树减掉）。

当 $r\le i+len'_l-1$ 时，即计算 $i\in[r-len'_l+1,r],\sum S_{min(r,i+len'_i-1)}$，按 $r$ 和 $i+len'_i-1$ 排序，使用扫描线可以解决。

否则 $i\in (l,r-len'_l]$，此时求 $\sum S_{min(i+len'_i-1,i+len'_l-1)}$，此时按重链从上至下的顺序扫描线，其他的用对称后缀树查询就可以了，复杂度 $O(n\log^2 n)$，期望得分 $100$ 分。另外，将线段树合并改为离线树状数组会快很多。

毛估估就行

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。