令走一步的 GF 是 \(S(t) = t^{-1} + \sum_{i=1}^k b_i t^{a_i}\)，则重复经过算多次的答案就是 \(\frac1{(1-S(1)z)^2}\)。
考虑容斥，令答案的 GF 为 \(F(z)\)。那么一个格子被经过多次等价于第一次经过后通过若干次操作返回。
设 \(G(z)\) 表示从原点开始，经过若干次操作返回原点的 GF，那么 \[
F(z) G(z) = \frac1{(1-S(1)z)^2} \iff F(z) = \frac1{(1-S(1)z)^2 G(z)}
\]
那么我们知道 \[ [z^n] G(z) = [t^0] S^n(t) \]
注意到 \(S(t) = \frac{1+\sum_{i=1}^k b_i t^{a_i+1}}t\)，设 \(u=\frac t{1+\sum_{i=1}^k b_i t^{a_i+1}}\)，则 \[ \begin{aligned} {} [z^n] G(z) &= [t^0] S^n(t) \\ &= [t^0] u^{-n} \\ &= [t^n] v' \cdot (t/v)\qquad\left(v = u^{\langle -1\rangle}\right) \end{aligned} \]
因此 \(G(z) = v'\cdot (z/v)\)。则 \[ \begin{aligned} {} [z^n] \frac1{(1-S(1)z)^2 G(z)} &= [z^n] \frac{v/z}{(1-S(1)z)^2 v'} \\ &= [z^n] \frac{ (v/z)^{n+2} }{(1-S(1)z)^2 v'^2} v' (z/v)^{n+1} \\ &= [z^n] \frac{ (z/u)^{n+2} u'^2 }{(1-S(1)u)^2} \end{aligned} \]
令 \(w=zS(z)\)，则 \(u=z/w\)，且上式 \[ \begin{aligned} &= [z^n] \frac{ w^{n+2} (z/w)'^2 }{(1-S(1)z/w)^2} \\ &= [z^n] \frac{(w-zw')^2}{(w-S(1)z)^2} w^n \end{aligned} \]
两边分别整式递推后暴力算一项卷积就是 \(O(kn)\) 的了。