写挂了 QwQ，但是思路是对的。

A

显然 $T \ge dk + d\min \{t_1,t_2\}$，$t_1 \le t_2$ 时可以取等，在原地等 $d$ 个铁然后直接出发即可。

$t_1 > t_2$ 不能取等。此时路径必然是多个折返，设距离 $d$ 的子问题答案为 $f(d)$，则

$$\begin{aligned} f(d) &= \min_{i=0}^{d-1} \max\{dk, f(i)+it_2\} + it_2 + (d-i)t_1 \\ &= dt_1 + \min_{i=0}^{d-1} \max\{dk+i(t_2-t_1), f(i)+i(2t_2-t_1)\} \\ &\mathop{=}\limits^{\text{换元}} dt_1 + \min_{i=0}^{d-1} \max\{A(d,i), B(i)\} \end{aligned}$$

众所周知，分段函数的最小值是每一段的最小值的最小值。$A(d,i)$ 关于 $i$ 单调递减，而 $B(i)$ 与 $d$ 无关，可以数据结构维护。因此只需知道如何分段。

$A$ 主导时

$$dk \ge f(i)+it_2 \mathop{=}\limits^{\text{def}} g(i)$$

因为 $g(i)$ 单调递增，$d$ 增加时分界点必不左移，可以直接挪分界点，不必二分。此时 $B(i)$ 相当于滑动窗口，单调队列维护即可。

单组测试数据时间复杂度 $O(m)$。

B

我们可以使用算子大大简化问题。记 $D f(x) = f'(x)$，因为 $D$ 是线性算子，记 $f(x)+f'(x) = (1+D) f(x)$。

$$F_{2k}(x) = \cdots(1+D)(1-D) F_0 (x) = (1-D^2)^k F_0(x ) \\ G_{2k}(x) = \cdots(1-D)(1+D) G_0 (x) = (1-D^2)^k G_0(x )$$

由二项式定理，

$$\begin{aligned} (1-D^2)^k f(x) = \sum_{i=0}^{k} (-1)^i \binom{k}{i} D^{2i}f(x) \end{aligned}$$

记 $[x^t]f(x)$ 为 $f(x)$ 的 $t$ 次项系数，则有

$$\begin{aligned} [x^t] (1-D^2)^k f(x) &= \sum_{i=0}^{k} (-1)^i \binom{k}{i} [x^t] D^{2i}f(x) \\ &= \sum_{i=0}^{k} (-1)^i \binom{k}{i} (t+2i)^{2i-}[x^{t+2i}]f(x) \\ &= \sum_{i=0}^{k} (-1)^i \binom{k}{i} \frac{(t+2i)!}{t!} [x^{t+2i}]f(x) \\ \end{aligned}$$

在 $t+2i > m$ 的时候直接 break，时间复杂度 $O(m^2)$。

以上是 $n$ 为偶数的情况，如果 $n$ 为奇数，可以先求 $F_{n-1}(x), G_{n-1}(x)$，最后一次运算 $O(m)$，可以直接暴力。