$x$段目の地面からの高さを$H_x$とし、$x$段目までの上り方の総数を$f(x)$とする。$H_l \ge H_x - P$となるような最小の段を$l$段目とするとき、$f$の漸化式は
$$ f(x) = \sum_{t \in [l, x)}f(t) $$と書ける。このままDPすると間に合わないので累積和$S(x) := \sum_{t=0}^xf(t)$を考える。
$$ f(x) = S(x-1) - S(l-1) $$ $$ S(x) = f(x) + S(x-1) $$が成り立つから、$S$の漸化式は
$$ S(x) = 2S(x-1) - S(l-1) $$とまとまる。$S$に関してDPすればよい。答えは$f(N) = S(N)-S(N-1)$である。
毎回$l$を二分探索で求めると計算量は${O}(N\log N)$。尺取り法で${O}(N)$。
