yukicoder No.802 だいたい等差数列

問題

単調増加数列 $A = (A_1, A_2, \dots, A_N)$ であって $A_N \le M$ かつ $L \le A _ {i + 1} - A _ i \le R$ なものの個数を数えよ。

単調増加数列と見たらとりあえず差分。$d_i = A _ {i + 1} - A_i$ とおく
$M$ 個の球を $N$ 個の箱にそれぞれ $L$ 個以上 $R$ 個以下の好きな数だけ配って好きな数余らせてよいときの配り方の数を求める問題になってる。やれば解ける
最初にそれぞれに $L$ 個配っておくことで $L = 0$ としてよい
$R$ 個以下しか配っちゃだめの制約が微妙に面倒。重複組合せ ${} _ n H _r$ とかですぐのはずだったが嘘っぽい
となると DP しかない。インラインをやる？
愚直な DP は $\mathrm{dp}(i + 1, j) = \sum _ {k \in [j - R, j]} \mathrm{dp}(i, k)$ である
補集合を数えて包除かな
DP の遷移を考えると $f = 1 + x + x^2 + \dots + x^R$ とおいて $f^N$ の $M$ 次以下の項の係数の総和が答えのはず。形式的冪級数って聞いてたのそういうことか？
初項の設定のために $g = 1 + x + x^2 + \dots + x^M$ をかける必要がありそう。

形式的冪級数をやりました。間に合いませんでした (手元最大ケース $7$ 秒)