問題： No.2670 Sum of Products of Interval Lengths - yukicoder
公式解説が天才っぽかったので、包除原理を使用したシンプルな解法を説明します。（多分最終的な結論は一緒ですが、導出が異なると考えています。）
数え上げるものは、値が $1$ ずつ増加する際の極大なブロックに分割したときの、各ブロックの長さの積の総和です。
極大なブロック間の仕切りを固定したときの答えを考えると、仕切りの左右の要素の差は $1$ ではないという制約が付きます。この制約は扱いづらいので包除原理で処理します。
仕切りのうち、仕切りの左右の要素の差は $1$ という制約が課された仕切りを青い仕切り、制約のない仕切りを赤い仕切りとして、赤い仕切りの位置を固定します。
赤い仕切り同士で区切られた長さ $n$ の区間にたいして青い仕切りを入れる方法全てに対する（包除原理の $-1$ 倍を含めた）答えへの寄与を $f_n$ とすると、$f_n=n-\sum_{i=1}^{n-1}i \times f_i$ という漸化式が立つので $f$ を $\mathrm{O}(N)$ で列挙できます。
（余談：実は $f$ は $(0,1,1,0,-1,-1,0,1,1,0,-1,-1,\ldots)$ と $6$ 個周期で繰り返していることが、漸化式を解くか実験をすることで分かります）
長さ $n$ の極大なブロックの個数を $g_n = \max(m-n+1,0)$ と置けば、求める答えは、形式的冪級数 $F(x) = \sum_{n=1}^{N} f_ng_nx ^ n$ として$[x ^ N] \frac{1}{1-F(x)}$ です。これは $\mathrm{O}(N\log N)$ で計算できます。
実装（の本質部分）
long long n, m;
array<mint, 6> f{0, -1, -1, 0, 1, 1};
int main() {
cin >> n >> m;
fps g(n + 1);
g[0] = 1;
for(int i = 1; i <= min(n, m); i++) g[i] = f[i % 6] * (m + 1 - i);
cout << g.inv()[n] << endl;
}
