1.13 练习

A Codechef LUCKYDAY

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

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

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

TkA=AT^{k}A = A

其中 AA 是初始的矩阵也就是

[a00b00100]\begin{bmatrix}a & 0 & 0\\ b & 0 & 0 \\ 1 & 0 & 0\end{bmatrix}

但是这里不等价于 Tk=eT^k = e 因为 AA 显然不满秩。

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

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

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

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

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

[x0z100001]\begin{bmatrix} x & 0 & z \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}

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

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

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

关于卡常。

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

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

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

B COT4 Count On A Trie

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

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

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

考虑如何做拼接操作。

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

C OnePointNineNine

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

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

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

\