2023“钉耙编程”中国大学生算法设计超级联赛（6）

1001. Count

题意：求满足 $A[1:k] = A[n-k+1:n]$ 的数组个数（值域为 $[1,m]$）

签到题，很容易发现原数组的循环节是 $n-k$，所以只要循环节内的数字确定即可，最终答案即为 $m^{n-k}$，输出即可，复杂度 $O(T\log n)$

~~场上不知道为啥一直在纠结 $k$ 和 $n-k$ 的大小关系，导致最终喜提 -3（虽然最终没啥太大影响的样子就是了）~~

1002. Pair Sum and Perfect Square

题意：给定一个排列，给定 $l,r$，求 $[l,r]$ 内满足 $p_i+p_j$ 为完全平方数的 $(i,j)$ 无序点对个数

首先很容易发现满足条件的点对数是 $O(n\sqrt{n})$ 级别的，将询问离线下来从左往右扫右端点就变成了单点 $+1$，区间求和的经典问题，其中修改数为 $O(n\sqrt n)$ 的，询问数为 $O(q)$ 的，修改数明显多于询问数，优先考虑分块，$O(1)$ 单点修改，$O(B+\frac nB)$ 区间查询，最终时间复杂度 $O(n\sqrt n+q(B+\frac nB))$，当 $B=\sqrt n$ 时取到最优复杂度 $O((n+q)\sqrt n)$，可以通过

1003. Vector

题意：给定四个三维向量 $A_1,A_2,A_3,A_4$，求是否存在非负实数 $x_1,x_2,x_3$ 满足 $x_1A_1+x_2A_2+x_3A_3=A_4$

分类讨论。考虑按向量的相关性分类讨论： - 当 $A_1,A_2,A_3$ 线性无关时：直接高斯消元即可 - 当 $A_1,A_2$ 线性相关，$A_3$ 与 $A_1,A_2$ 线性无关时：四个向量共面 - 当 $A_1,A_2$ 同向时：用 $A_2,A_3$ 高斯消元即可 - 当 $A_1,A_2$ 反向时：$A_3$ 与 $A_4$ 在 $A_1,A_2$ 同侧 - 当 $A_1,A_2,A_3$ 两两线性相关时： - 三个向量同向：$A_4$ 与 $A_1$ 同向 - 否则：$A_4$ 与 $A_1$ 共线即可

说了这么废话，其实也可以直接枚举 ${A_1,A_2,A_3}$ 的子集，每个高斯消元一下，有一个有解即可 ~~（本质就是乱搞，毕竟数据很小）~~，最终复杂度 $O(T*可过)$ 即可

1004. Tree

题意：有一棵树，每个点有一个颜色 $a/b/c$，统计 $a,b,c$ 三种颜色出现次数相同的简单路径数

经典路径统计问题，直接 dsu on tree/点分治即可，具体来说就是用 $(cnt_a-cnt_b,cnt_b-cnt_c)$ 作为桶的下标，用 $(cnt_b-cnt_a,cnt_c-cnt_b)$ 查询一个点对应的链能匹配的链的个数即可，点分治就是直接做，dsu on tree 可能需要加一个零点偏移，复杂度都是 $O(n\log n)$，可以通过

1005. Meadow

题意：求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m sumL_{i,j}*B_{i,j} {\rm\ mod\ }1e9+7$，其中 $sumL_{i,j}$ 表示覆盖 $(i,j)$ 的所有不同的全 $1$ 正方形的边长和

首先，所有的全 $1$ 正方形是 $O(n^3)$ 级别的，所以正方形一定是没办法枚举的，需要想办法分类统一处理

首先考虑按右下角的位置分类，可以发现满足条件的全 $1$ 正方形的边长构成了一个类似 $[1,r_{i,j}]\mathbb Z$ 的连续区间，其中 $r{i,j}$ 可以通过一个简单的 dp 得到

接下来考虑对于 $[i-r_{i,j}+1:i,j-r_{i,j}+1,j]$ 这个方形内的所有点，这些以此为右下角的方形产生的贡献，可以发现会变成子矩阵矩阵加一个类似这样的图样 $$\begin{matrix} r_{i,j} & r_{i,j} & \cdots & r_{i,j} & 0\ r_{i,j} & r_{i,j}+(r_{i,j}-1) & \cdots & r_{i,j}+(r_{i,j}-1) & 0\ \vdots & \vdots & \ddots & \vdots & \vdots\ r_{i,j} & r_{i,j}+(r_{i,j}-1) & \cdots & \frac{r_{i,j}(r_{i,j}+1)}2 & 0\ 0 & 0 & \cdots & 0 & 0\ \end{matrix}$$ 将这个加的矩阵二维差分一下，就可以得到如下的矩阵 $$\begin{matrix} r_{i,j} & 0 & \cdots & 0 & -r_{i,j}\ 0 & r_{i,j}-1 & \cdots & 0 & -(r_{i,j}-1)\ \vdots & \vdots & \ddots & \vdots & \vdots\ 0 & 0 & \cdots & 1 & -1\ -r_{i,j} & -(r_{i,j}-1) & \cdots & -1 & \frac{r_{i,j}(r_{i,j}+1)}2\ \end{matrix}$$ 很明显差分的矩阵可以分成三个等差数列和一个点，三个等差数列可以二阶差分之后变成三个单点的加减，所以最终需要的操作就变成了 $10$ 次单点加减，最后做三个一维二阶后缀和和一个二维一阶前缀和即可，复杂度 $O(\sum Cn^2)$，其中 $C$ 为常数，可以通过（注意加快读）

1006. Perfect square number

题意：给定序列 $a$，求改变其中一个数，最多可以使多少个区间的和为完全平方数

考虑对于数改变的位置 $p$，其改变会造成影响的区间一共有 $O(n^2)$ 个，而最终可能的完全平方数的结果可能有 $O(n)$ 个，所以我们可以先 $O(n^2)$ 预处理出所有改变区间在去掉 $a_p$ 之后的原始值，然后枚举 $a_p$ 变成的值，再枚举每个完全平方数去桶里收集答案，就可以在 $O(n^2)$ 的时间复杂度内求出改动 $a_p$ 的答案，再枚举所有 $a_p$ 取 $max$ 即可，复杂度 $O(n^3+nV\sqrt{nV})$，其中 $V$ 代表值域大小，由于 $n,V$ 同阶，可以将复杂度化简为 $O(n^3)$，可以通过

1007. Competition

1008. Alice and Bob

题意：二人博弈，每个人一次操作会选择一个位置将原序列分成两段长度不为 $0$ 的序列，剩下较大的那一段，无法操作的一方胜利，必胜的人会最大化剩下的数，必败的人则会最小化剩下的数，求最终剩下的数的结果

博弈论 dp，定义 $win_{l,r}$ 表示剩下 $[l,r]$ 时先手必胜/必败，$dp_{l,r}$ 表示 $[l,r]$ 最后会剩下的数，直接转移复杂度是 $O(n^3)$ 的，很容易发现对于一段区间 $[l,r]$，其前驱状态是类似这样的：$[l+1,r],[l+2,r],...,[pos,r],[l,pos+1],...,[l,r-2],[l,r-1]$，且对于相同的 $l/r$，$pos$ 的位置是单调的，于是就可以每个点分别开两个从左到右的单调队列和从右到左的单调队列分别维护前缀最大、前缀最小、后缀最大、后缀最小转移即可，复杂度 $O(Tn^2)$，可以通过

注：\ 其实实际可以将 $4n$ 个单调队列缩减为 $2n$ 个，因为如果一个状态是必胜态的话，其可能的后继必败态最多有两个（一个必败态的前驱和后继一定都是必胜态），但复杂度上没什么优化，码量也差不了多少，就当是一个小结论记住吧。

1009. Coloration

1010. Calculate

题意：给定一个环森林，一个人从 $x$ 开始游走 $l$ 步，每到一个节点，自己手中的权值 $y$ 就会变为 $k_iy+b_i$，求该人游走完毕后手中权值的大小，$q$ 次询问

首先很明显先后两次操作 $(k_i,b_i),(k_j,b_j)$ 可以合为一个 $(k_ik_j,k_jb_i+b_j)$，然后对于多次相同的合并，由于合并的运算满足结合律，可以考虑倍增求解，复杂度 $O((n+q)\log l)$

1011. String

题意：给定一个文本串 $S$ 和多个模式串 $T$，对每个模式串求随机选择模式串的一个子串，其在文本串的多少子串中出现过的期望值

首先可以对 $S$ 建 SAM，让 $T$ 在 SAM 上跑，这样就可以将 “ $T$ 的子串在 $S$ 的多少子串中出现过 ” 这个问题转化为 “ $S$ 的每个子串在 $S$ 的多少子串中出现过 ”，然后对于询问，直接在 SAM 上跑，每次求一个链前缀和即可。链前缀和可以 $O(n)$ 预处理，所以答案就变成了求 “ $S$ 的每个子串在 $S$ 的多少子串中出现过 ” 这个问题的答案

容易发现上述问题可以进一步转化为这样的一个问题：给你一些长度相同区间，求有多少区间覆盖了其中的任意一个区间，这个问题的答案可以通过求其逆命题，即不覆盖任意一个区间得到，所以对于节点 $u$ 的长度为 $len$ 的子串的最终答案就是这个式子： $$\frac{n(n+1)}2-\sum\limits_{i=0}^{cnt}\left(\frac{(r_{i+1}-r_i+len-2)(r_{i+1}-r_i+len-1)}2-2\right)$$ 其中 $r_0=len-1,r_{cnt+1}=n+1,r_i \in endpos(u)$

很明显这个式子可以拆成类似 $k*len+b$ 的形式，而对于一个节点的所有字符串的 $len$ 都是连续的，所以只要求出每个节点的 endpos 集合并在求这个集合的时候动态维护 $k,b$ 的值即可求出每个点对应所有子串的答案的和，做法有很多，线段树合并、dsu on tree 等均可，复杂度 $O(Tn\log n) \sim O(Tn\log^2n)$，可以通过