形式的冪級数（FPS）が使える AtCoder の問題リスト（随時更新）

$1$ 駅以上 $K$ 駅未満連続して止まることと，$1$ 駅以上連続して止まらないことを交互に繰り返します．そこで，$z$ を不定元とする冪級数を\begin{align*}f := \sum_{i=1}^{K-1} z^i &= \frac{z - z^K}{1 - z},\\ g := \sum_{i=1}^{\infty} z^i &= \frac{z}{1 - z} \end{align*}と定めると，問題の答えは，\begin{align*} f + fgf + fgfgf + \cdots &= \frac{f}{1-fg} \\ &= \red{\frac{(1-z)(z - z^K)}{1 - 2z + z^{K+1}}} \end{align*}の $z^N$ の係数に等しいです（途中計算は Wolfram Alpha に投げるとよいです）．これは「係数がスパースな冪級数用の乗除算」を使うことで，計算量 $O(N)$ で計算できます．

$z$ を不定元とする冪級数を\[g_i(x_i) := \sum_{a=0}^\infty (x_i z)^a = \frac{1}{1 - x_i z}\]と定めると\[f(x_1, \dots, x_N) = [z^C] \prod_{i=1}^N g_i(x_i) \]です．よって問題の答えは，\begin{align*} \sum_{x_1,\dots,x_N} f(x_1,\dots,x_N) &= [z^C] \sum_{x_1,\dots,x_N} \prod_{i=1}^N g_i(x_i) \\ &= \red{[z^C] \prod_{i=1}^N \bigg( \sum_{x_i = A_i}^{B_i} g_i(x_i) \bigg)} \end{align*}となります．これを愚直に計算すると計算量は $O(NC(C + \max_i B_i))$ となり，十分高速です．

$z$ を不定元とする多項式を $f := z^0 + z^A + z^B + z^{A+B}$ と定めると，問題の答えは $[z^K] f^N$ です．これの計算は一見難しそうですが，$f$ をぐっと睨むと，$f = (1 + z^A)(1 + z^B)$ と因数分解できることに気づきます．よって，二項定理を使うと\begin{align*} [z^K]f^N &= [z^K] \bigg ( \sum_{x = 0}^N \binom{N}{x} z^{Ax} \bigg) \bigg ( \sum_{y = 0}^N \binom{N}{y}z^{By} \bigg) \\ &= \red{\sum_{(x, y):\, Ax + By = K} \binom{N}{x} \binom{N}{y}} \end{align*}と変形でき，これは $O(N)$ 時間で計算できます．