枪打出头鸟

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⩾j]$，答案就是 $tr(M^n)$

​ 熟知，$tr(M^n)=\sum {\lambda }_i^n$

​ 由牛顿恒等式或者由幂和的推导，不妨设矩阵的特征多项式为 $F$，则 $tr(M^n)=[x^n]\frac{(F^{\prime }{)}^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^{\prime }{)}^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$ 的情况。

设 $p{t}_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]$ 中的出现次数， 我们从后向前建立后缀自动机，那么答案即为后缀树上 $p{t}_l$ 到根的每一个点的 $(le{n}_i-le{n}_{f{a}_i})\times |Righ{t}_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$，枚举一个长度 $le{n}^{\prime }\in [le{n}_{f{a}_y}+1,le{n}_y]$，那么就在其子树查询 $[l,r-le{n}^{\prime }+1]$ 的点数。

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

算法 4

解决数据随机的情况。

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

对正序串对称建立后缀自动机，设当前点代表的后缀为 $p$，找到 $[p,p+le{n}^{\prime }-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}^n{S}_{j+lcp(l,j)-1}$。考虑树链剖分，设 $p{t}_j$ 表示后缀 $j$ 代表的点，对于 $p{t}_j$ 的祖先和一条重链的交的最深的点 $x$，对于 $x$ 的重儿子的子树，要求 $\sum _{j>l}{S}_{j+le{n}_x-1}$，使用算法 4 对称后缀树的做法即可。

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

最后，要减去 $p{t}_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)}$。

同样使用 $dsuontree$，设 $p{t}_l$ 与重链的交为 $x$，那么要求 $j$ 与重链的交在 $x$ 的上方，求 $S_r\times \sum _{j\in (l,r]}[le{n}_j^{\prime }+j-1\ge r]+\sum _{j\in (l,r]}[le{n}_j^{\prime }+j-1<r]S_{le{n}_j^{\prime }+j-1}$。

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

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

算法 8

idea from mayaohua

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

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

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

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