题解_牛客博客

A

注意到当 $s$ 不是全 $0$ 串时，基本可以变成任意一个 $01$ 串，具体的思路就是先把 $s$ 变为全 $1$ 串（ $01/10\rightarrow 11$ ），然后再变成想要的串。但是会有反例，注意到至少操作了一次的串至少存在一个 $x$ ，满足 $x,x+1$ 这两个位置上的值一样，所以说一定变不了 $0101010\cdots$ 或者 $10101010\cdots$ 这种串，且反例只有这个。

B

发现其实就是要求 $f_{k-1,l}\oplus f_{k-1,r+1}$ 。

类似于杨辉三角，有 $f_{k, j} = \bigoplus_{p=0}^{k-1} \binom{k-1}{p} a_{j+p} \pmod 2$ 。

直接计算即可，时间复杂度 $\mathcal{O}(\sum k)$ 。

C

$\mathcal{O}(n\log_2 V)$ 的做法跑的太快了，不知道咋卡。

讲讲我期望的做法吧。

可以发现一个子区间的美丽度只有 $1,2,3$ 三种可能，因为 $\gcd$ 每次不变或至少除 $2$ 。

一个子区间的答案为 $1$ 当且仅当这个子区间的 $\gcd\ne 1$ ，设 $R_i$ 为满足左端点为 $i$ ，右端点最远到 $R_i$ 满足这个子区间的 $\gcd\ne 1$ 。

怎么快速求 $R_i$ 呢，显然直接二分会 tle，考虑对每个数分解质因子，然后倒着扫，维护每种质因子当前能够延伸出去的最远位置，那么 $R_i$ 就为 $A_i$ 所包含的那些质因子能够延伸出去的最远位置的 $\max$ 。

如何判断一个子区间的美丽度是否为 $3$ ？

设 $R_{2_i}$ 为满足左端点为 $i$ ，右端点最远到 $R_{2_i}$ 满足这个子区间的 $\gcd\ne 1$ （除去 $2$ 这个质因子）。

设 $b_i$ 为 $A_i$ 所含 $2$ 的质因子个数。

首先得出现 $1$ 和 $2$ ， $1$ 就是这个子区间的 $\gcd=1$ （除去 $2$ 这个质因子），难点在于判断出现 $2$ ，可以发现前缀 $\gcd$ 为 $2$ 的右端点也是一段区间（如果存在），只需要找到这个区间的左端点。

一个符合条件的右端点条件有两个：

这个位置要在 $R_{2_i}$ 之后。
这个子区间的 $b_i$ 的最小值为 $1$ 。

开个指针倒着扫一遍即可。复杂度为 $\mathcal{O}(f(V)n)$ ，其中 $f(A)$ 表示 $1\sim A$ 中不同质因子种数的最大值， $f(5\times 10^6)=7$ ，可以接受。

D

确实是简单优化建图题啊，没什么难度。

容易想到将边看成一个点，那其实就好做了。

设关键指针值集合 $S_u$ 包括：起点 1 的初始值 0，对于每条连接 $u, v$ 的边的颜色，

作为出边的要求值： $(c - b_u) \pmod P$ 。即我们必须在 $u$ 点将指针调整到此值才能进入该边；作为入边的到达值： $(c - b_v) \pmod P$ 。即如果从 $v$ 点进入该边，到达 $u$ 时指针会停留在 $v$ 点出发时的值。

对于每个点 $u$ ，在 $S_u$ 的相邻值之间建立双向边，形成一个环。边权为两个颜色值的环形距离 $\min(|x-y|, P-|x-y|)$ 。这对应在节点 $u$ 处花费代价调整指针。

对于原图边 $(u, v, c)$ ，令 $val = (c - b_u) \pmod P$ 。我们在 $u$ 处调整好指针到 $val$ 后，经过边到达 $v$ ，指针仍为 $val$ 。因此，建立有向边： $State(u, val) \to State(v, val)$ ，权值为 0。

最后跑一个 dijkstra 即可。

E.

答案容易写成：

\sum_{p∈P} \sum_{l=1}^p \sum_{r=p+L-1}^n \sum_{k=l}^r b_k

其中 $P$ 是 $S$ 在原串 $a$ 中的所有起始位置集合， $L = y-x+1$ 。

令 $f(X,Y)=\sum_{l=1}^X \sum_{r=Y}^n \sum_{k=l}^r b_k=(n-Y+1)F_X + X c_n + X F_Y$ 。

其中 $F_i=\sum_{k=1}^i kb_k-ib_k$ 。

注意到 $X$ 与 $Y$ 的关系是 $Y-X=p$ 。那么 $(n-Y+1)F_X$ 可以直接通过正串 SAM 进行计算，同样的 $XF_Y$ 通过反串 SAM 进行计算即可。

如果没有看出这一点，可能会去想分块 NTT。

F.

qanalog 简单练习题。

alt

考虑转换为格路计数，不妨假设让路径在 $y=x$ 的上方，那么 $alice(s)$ 实际上就是路径与 $y=x$ 之间围成的整格数加上 $\frac{n(n-1)}{2}$ 。考虑如何刻画 $bob(s)$ ，注意可以看作从原点出发，先一直往上走，直到碰到了路径或者 $y=x$ 就改变方向。 $bob(s)=n-i+(n-i-j)+...$ 。

考虑 $dp_{n,i}$ 表示从 $(0,0)$ 走到 $(n,n)$ 且第一次碰撞时上升的高度为 $i$ （就是图中所画的）的所有路径的贡献之和。容易写出转移

dp_{n,i}=\sum_{j}B^{n-i}dp_{n-i,j}\binom{i+j-1}{i}_A A^{\binom{k}{2}}

这个玩意容易写成一个差卷积的形式，于是可以做到 $\mathcal{O}(n^2\log n)$ 。

请注意在 $A$ 的阶小的时候直接卷是错的，因为这个时候 $q^k=1$ 可能发生，使用 q-Lucas 定理处理即可。