P12814 [NERC 2021] Admissible Map

一个**地图**是由符号集 $\{\texttt{U}, \texttt{L}, \texttt{D}, \texttt{R}\}$ 中的符号组成的矩阵。 地图矩阵 $a$ 的**地图图集**是一个有向图，包含 $n \cdot m$ 个顶点，编号为 $(i, j)$（$1 \le i \le n$；$1 \le j \le m$），其中 $n$ 是矩阵的行数，$m$ 是矩阵的列数。该图有 $n \cdot m$ 条有向边 $(i, j) \to (i + di_{a_{i, j}}, j + dj_{a_{i, j}})$，其中 $(di_U, dj_U) = (-1, 0)$；$(di_L, dj_L) = (0, -1)$；$(di_D, dj_D) = (1, 0)$；$(di_R, dj_R) = (0, 1)$。当地图图集中的所有边都指向图中的有效顶点时，该地图图集是**有效的**。 一个**可容许地图**是指其地图图集有效且由一组环构成的地图。 地图 $a$ 的**描述**是地图所有行的拼接——即字符串 $a_{1,1} a_{1,2} \ldots a_{1, m} a_{2, 1} \ldots a_{n, m}$。 给定一个字符串 $s$，你的任务是找出该字符串中有多少个子串可以构成某个可容许地图的描述。 字符串 $s_1s_2 \ldots s_l$ 的**子串**由一对索引 $p$ 和 $q$（$1 \le p \le q \le l$）定义，等于 $s_ps_{p+1} \ldots s_q$。当两个子串的索引对 $(p, q)$ 不同时，即使它们表示相同的字符串，也被认为是不同的子串。

唯一的输入行包含一个字符串 $s$，由至少 1 个、最多 $20\,000$ 个符号 $\texttt{U}$、$\texttt{L}$、$\texttt{D}$ 或 $\texttt{R}$ 组成。

输出一个整数——能够构成某个可容许地图描述的 $s$ 的子串数量。

在第一个例子中，有两个子串可以构成可容许地图的描述——$\texttt{RDUL}$ 作为 $2 \times 2$ 的矩阵（图 1）和 $\texttt{DU}$ 作为 $2 \times 1$ 的矩阵（图 2）。 在第二个例子中，没有任何子串可以构成可容许地图的描述。例如，如果我们尝试将字符串 $\texttt{RDRU}$ 视为 $2 \times 2$ 的矩阵，可以发现生成的图不是一组环（图 3）。 在第三个例子中，三个子串 $\texttt{RL}$、两个子串 $\texttt{RLRL}$ 和一个子串 $\texttt{RLRLRL}$ 可以构成可容许地图，其中某些子串有多种方式。例如，子串 $\texttt{RLRLRL}$ 可以表示为 $3 \times 2$ 的矩阵（图 4）或 $1 \times 6$ 的矩阵（图 5）。   翻译由 DeepSeek V3 完成