AtCoder Beginner Contest 284

ABC 挺娱乐的，找找手感

Source

AtCoder Beginner Contest 284

D - Happy New Year 2023

$p, q$ 之中至少有一个小于等于 $^3\sqrt{9\times10^{18}}$，筛法即可

E - Count Simple Paths

直接暴力 DFS

F - ABCBAC

看到有用字符串哈希做的。这里使用 Z 算法（国内又称扩展 KMP）

对于长度为 $n$ 的串 $S[0\cdots n - 1]$，Z 函数定义为 $Z[i] := \text{LCP}(S[i\cdots n], S), Z[0] = 0$

令 $S = \rightarrow\Rightarrow$，其中 $\rightarrow, \Rightarrow$ 表示字符串。则 $T$ 应该能被表示为 $\rightarrow\Leftarrow\leftarrow\Rightarrow$

假设 $T$ 如此。令 $U = \rightarrow\Leftarrow\Leftarrow\rightarrow, V = \Leftarrow\rightarrow\rightarrow\Leftarrow$。只需求 $U, V$ 的 Z 函数，然后对 $[n, 2n - 1]$ 的每个位置判断一下即可

Warnings

• $\sqrt{9\times10^{18}}$ 取了 $2\times10^6$，无语了