1.13 练习

A Codechef LUCKYDAY

阴间题。除开卡常和细节还是道很好的题。

$L,R \le 10^{18}$ ，会想到寻找循环节。由于下一个数会和前两个数有关，因此循环结最大不会超过 $p^2$ ，也就是 $10^8$ 级别。但是这个数是可以卡满的，而这题 $500\text{ms}$ 显然不会放过去暴力。

如何找循环节呢，考虑这个转移写成矩乘，设转移矩阵是 $T$ ，于是问题就变成了找最小的 $k$ 使得

$T^{k}A = A$

其中 $A$ 是初始的矩阵也就是

$\begin{bmatrix}a & 0 & 0\\ b & 0 & 0 \\ 1 & 0 & 0\end{bmatrix}$

但是这里不等价于 $T^k = e$ 因为 $A$ 显然不满秩。

我们可以 考虑做一次矩阵 BSGS 来找到循环节。这里复杂度是 $O(P)$ 的，具体来说先把 $T^xA,P | x$ 做 Hash 存进 Hash 表，然后把 $k$ 拆成 $xP - t$ 枚举 $t$ 来查是否存在 $T^t A$ 这个东西。

然后再考虑如何求出一次循环节中的 $c$ 出现的位置。我们考虑枚举 $c$ 的上一个数 $x$ ，于是就成了寻找循环节中 $c,x,1$ 这样的矩阵是否出现过，显然一个循环节中最多只会出现一次。这个我们仍然可以类似刚刚的进行矩阵 BSGS 也就是写成 $T^xA = B$ 的形式来做。

由于我们需要枚举 $O(P)$ 个 $c$ 的上一个位置，设步长为 $x$ ，复杂度就是 $O(Px + \frac{P^2}{x})$ ，显然 $x = \sqrt P$ 的时候最优。这样复杂度就优化到了 $O(P\sqrt P)$ 这样的东西。

然后这题还有特殊情况以及卡常。先说说特殊情况。

如果 $y = 0$ ，那么转移矩阵就是

$\begin{bmatrix} x & 0 & z \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

这个矩阵好像不满秩！不管怎么乘，也不一定能乘回单位矩阵，其实仔细思考一下也是，如果递推式是 $f_i = xf_{i-1} + z$ ，这个递推式就和 $f_1$ 无关了，如果后面循环显然不一定能循环回 $f_1 , f_2$ 。

但是这种情况显然循环节大小不超过 $P$ ，所以可以暴力跑。

由于还要考虑 $x = 0$ 的情况，一种比较方便的解决方式是从第三个数开始找循环节。

关于卡常。

首先这题不能用 unordered_map 之类的，还是得拉链 Hash 不然卡不过去。

然后矩阵乘法是可以优化的，由于 $P \le 10^4 + 7$ 我们显然可以把矩阵乘法乘完了再一起模，取模次数从 $O(N^3)$ 变成了 $O(N^2)$ 。

然后我的一种卡过去的方式是，先用 $O(P)$ 来算循环节，然后用循环节的 $\frac 1 4$ 次方来做，会快一些。

B COT4 Count On A Trie

我们考虑把所有 $S,T$ 中的串全部反过来。

于是我们直接对题目中给的 $S$ 的 trie 建立 SAM 就得到了所有 $S$ 的串构造出的后缀树。同时这个东西的叶子的 dfs 序排序就是后缀排序。

然后我们考虑把所有 $T$ 对应到 $S$ 的 SAM 上的某个节点，于是往前加字母就是在 SAM 上走，往后加字母就是在后缀树上走。

考虑如何做拼接操作。

考虑我们要把 $T_i,T_j$ 拼接成 $T_iT_j$ 作为新的一个 $T$ 。考虑 $T_i$ 在后缀树上的节点是 $u$ ，那么 $T$ 所在的节点必然在 $u$ 子树之内。我们考虑把子树内的叶子写成一个序列，那么 $T_i$ 可以对应到 $[l,r]$ 表示一个极大的区间使得区间的所有串的 LCP 是 $T_i$ 。我们尝试二分一下 $T_j$ 的左端点和右端点。比如二分左端点，我们可以二分出一个叶子位置 $x$ ，现在需要看一看 $x$ 位置的字符串除开 $T_i$ 这个前缀后得到的串和 $T_j$ 的大小关系，这个就是在 trie 上跳 $k$ 级祖先。我们需要找到小于 $T_j$ 的最大的以及大于 $T_j$ 最小的即可。

C OnePointNineNine

如果画一下图会发现，有很多点的所有邻居都是相同的。我们可以把这些点缩起来。然后可以证明的是，如果把距离不到 $D$ 的点连起来，得到的东西所有点度数不超过 $2$ 。

首先可以发现，对于任意两点 $u,v$ 如果它们的距离不超过 $0.99D$ ，那么一定会被缩起来。因为考虑如果有一点 $w$ 满足 $|wu| \le D , |wv| > 2D$ ，显然 $|wu| + |uv| < |wv|$ ，不可能成立。所以对于任意两点 $uv$ 如果有边，那么一定有 $|uv| \in [1.99D,2D]$ 。然后讨论一下 根据PPT有 当距离不超过 $1.94$ 都是对的。

于是直接对换和链分别做 $dp$ 即可。