既然超过 \(S \cdot T\) 的空地不会改变青蛙的“记忆模式”，我们就可以把任意长的空地**缩短成 \(S \cdot T\)**，而不影响最终答案。
例如，若石子在 100 和 10000 处，中间 9900 格全是空的，我们只需保留 90 格（因 \(S,T \leq 10\)，取 \(10 \times 9 = 90\)）。压缩后，DP 状态空间大小从 \(L\)（可能 10⁹）降到约 \(100 \times 90 = 9000\)，计算可行。**这个 \(S \cdot T\) 就是保证状态“线性无关组已完备”的临界长度**。

假设两块石子之间全是空地，距离为 \(d\)。青蛙能跳 \(S, S+1, \dots, T\) 格。数学上可以证明：只要 \(d > S \cdot T\)，青蛙就能通过不同跳法，**落到这段空地之后的任意“相对位置”**（比如刚好对齐某个余数）。
这是因为步长集合能“生成”所有足够大的数（因 \(\gcd=1\)），而 \(S \cdot T\) 是最坏情况下需要的最小长度（来自 Frobenius 问题）。此时，状态向量 \(\mathbf{v}_x\) 已经遍历了所有可能的组合，**新增的空地不会带来新信息**——就像背完乘法表后，再背也是重复。

青蛙跳到位置 \(x\) 时，最少踩多少石子，只和它**前 \(T\) 步**的情况有关（因为最多跳 \(T\) 格）。我们可以把这 \(T\) 个值写成一个“状态向量”：
\[
\mathbf{v}_x = \begin{bmatrix} f(x-T+1) \\ f(x-T+2) \\ \vdots \\ f(x) \end{bmatrix}
\]
这个向量就像青蛙的“记忆”，长度固定为 \(T\)。所以，不管桥多长，所有可能的“记忆”最多只有 \(T\) 个独立方向——这叫**状态空间维度不超过 \(T\)**。一旦走过一段很长的空地，这些“记忆”就会开始重复。

以下内容是根据陈老师讲的后增加的自我总结的内容

水题

双倍经验：
http://218.28.19.228:8081/cogs/problem/problem.php?pid=vNxXmkqqa
1440. [NOIP 2013]积木大赛

回复 @ムラサメ :
文明 @回归运动

数据说明错误
在数据说明板块中，对m和colori的描述为"1<=m<=10000,1<=colori<=",
其中colori缺少最大数，
应该为"1<=m<=10000,1<=colori<=m"或"1<=colori<=m<=10000"。

$ 举个例子，假如你现在遇到的string-b中的元素分别为 1，2，3，4，*，1，2，3，4；$
在第一层循环时 $ a[1] = b[j] $
在下一次时 $ a[i] *= 10 $ $ a[i]+=b[j] $

此时 $ j=1 $
$ a[i]=1*10+2=12 $

同时第三次时

此时 $ j=2 $
$ a[i]=12*10+3=123 $

同时第四次

此时 $ j=3 $
$ a[i]=123*10+4=1234 $

注意，后面我们遇到的符号 ，所以我们将保存数据到一个全新的 $ 数组- c $ 中，其中 $ jsq $ 在判断到遇到符号所以jsq在存储完后加上2（一个存上一个数字，一个存这次的符号）

此时 $ jsq=2 $
$ c[1]=1234 c[2]=* $

说句闲话：http://172.30.1.3/cogs/submit/code.php?id=7SzeaWqgk 5 9 4 7 行 代 码 但没事了我们写出整正解了

回复 @hsl_beat :
啊？我上次交了一个2000行的html小游戏都说文件太大了，大佬求教程

可以不开longlong，我的话是用了一个string，然后先分离，在分离数字时可以搞一个int变量，在遇到数字时直接加上，下一次先乘以10再直接加上就好了，当然这些是扫到数字的时候的时候执行的，当遇到符号的时候就直接让那个int定量加一下，例如刚开始是a[i]，扫到符号后下一次遇到数字就存到a[i+1]

要开longlong啊

阴

来源里的璃月港算法竞赛太细节了

好难啊

- 通行后到达时间为 $T'' = T' + 1$，余数为 $(r + 1) \bmod k$；
- 用 $T''$ 更新 $d[v][(r+1) \bmod k]$。
最终答案为 $\min_{0 \leq r < k} d[n][r]$。

有 $n$ 个景点、$m$ 条道路，巴士每 $k$ 分钟一班。每条道路有开放时间 $t_{\text{open}}$，仅当当前时间 $\geq t_{\text{open}}$ 时可通过，通行耗时 1 分钟。求从景点 $1$ 到景点 $n$ 的最早到达时间。
**思路**：
设 $d[i][r]$ 表示到达景点 $i$ 时，当前时间模 $k$ 余 $r$ 的最早绝对时间。初始状态 $d[1][0] = 0$。
对每条边 $(u, v, t_{\text{open}})$，若当前时间为 $T = d[u][r]$，则：
- 若 $T < t_{\text{open}}$，需等待至首个 $\geq t_{\text{open}}$ 的发车时刻：
等待后时间 $T' = \left\lceil \frac{t_{\text{open}} - T}{k} \right\rceil \cdot k + T$；

化简核心分两步：
1. **有理数根**：若 $\Delta$ 为完全平方数，计算分子 $-b \pm \sqrt{\Delta}$（按 $a$ 正负取较大根），分母 $2a$，用 $\gcd$ 约分为最简分数。
2. **无理数根**：将 $\sqrt{\Delta}$ 化为 $k\sqrt{r}$（$r$ 无平方因子）：枚举 $i=2$ 到 $\lfloor\sqrt{\Delta}\rfloor$，若 $i^2 \mid \Delta$，则 $\Delta \gets \Delta / i^2$，$k \gets k \cdot i$。最终根为 $\frac{-b}{2a} + \frac{\pm k}{2a}\sqrt{r}$，分别约分两部分，确保无理系数为正，按格式输出。