DPを考えます。

\(0 \leq i \leq N\) に対して

• \(dp0[i]\): 総和 \(i\) の素晴らしい整数列の個数
• \(dp1[i]\): 総和 \(i\) の素晴らしい整数列の全てに対する長さの総和

とします。

数列をランレングス変換したものを数え上げることにすると、包除原理を用いて次のような遷移を書けます。

• \(f(j)\): 同じ整数をいくつか使った総和 \(j\) の整数列を考えたとき、条件を違反する個数を \(k\) としたときの \((-1)^k\) の総和
• \(g(j)\): 同じ整数をいくつか使った総和 \(j\) の整数列を考えたとき、条件を違反する個数を \(k\)、長さを \(l(=k+1)\) としたときの \((-1)^k \times l\) の総和
• \( \displaystyle dp0[i] = \sum_{j=1}^{i} f(j) \times dp0[i-j]\)
• \(\displaystyle dp1[i] = \sum_{j=1}^{i} g(j) \times dp0[i-j] + f(j) \times dp1[i-j]\)

\(f(j)\) や \(g(j)\) は、調和級数のテクで \(O(N \log N)\) で計算できますが、DPの計算に \(O(N^2)\) かかってしまいます。

実装例(C++, TLE): https://atcoder.jp/contests/abc297/submissions/40510083

そこで、分割統治FFTをすると \(O(N \log^2 N)\) で計算できます。分割統治FFTについては https://atcoder.jp/contests/abc213/editorial/2396 などが参考になります。

実装例(C++, AC): https://atcoder.jp/contests/abc297/submissions/40510739

FPS の inv を使うことで \(O(N \log N)\) でも解けます。