yukicoder 802 だいたい等差数列

https://yukicoder.me/problems/no/802

Let us find the number of \(x_1, \ldots, x_N\) such that \(x_1 + \cdots + x_N \le M\) and \( x_1 \ge 0\), \(0 \le x_i \le D_2-D_1 \) for \(2\le i \le N\). The generating function can be written as

\begin{align}
(1+x+\cdots+x^{D_2-D_1})^{N-1} \times (1+x+x^2+x^3+x^4+\cdots)^2.
\end{align}

Thus, the answer is

\begin{align}
[x^M] \left( \frac{(1-x^{D_2-D_1+1})^{N-1}}{(1-x)^{N+1}} \right).
\end{align}

The coefficient of \(1/(1-x)^n\) can be computed quickly using the H(n,r). I think inclusion exclusion is simpler than this.