私の形式的べき級数解説 (1) の【問題14】あたりを真似して、形式的べき級数を利用した立式をします。

• \(a_1 - 0\) に対応：\(1/(1-x) = 1 + x + x^2 + x^3 + \cdots\)
• \(a_{i+1}-a_i\) に対応：\(f = x^1+x^2+x^4+x^5+x^7+x^8+\cdots\)
• \(M - a_N\) に対応：\(1/(1-x) = 1 + x + x^2 + x^3 + \cdots\)

として、答えは次のように表せます：

\[[x^M]1/(1-x)^2\cdot f^{N-1}\]

\(f\) は、次のように有理式で表せます：

\[f=\biggl(\sum_{n=0}^{\infty}x^n\biggr)-\biggl(\sum_{n=0}^{\infty}x^{3n}\biggr) = \frac{1}{1-x}-\frac{1}{1-x^3} = \frac{x+x^2}{1-x^3}\]

したがって、答えは次のようになります。

\[[x^M] (x+x^2)^{N-1}\cdot \frac{1}{(1-x^3)^{N-1}}\cdot \frac{1}{(1-x)^2}\]

\(F = (x+x^2)^{N-1}\), \(G = \frac{1}{(1-x^3)^{N-1}}\) として、答は \([x^M]\bigl(F\cdot \frac{G}{(1-x)^2}\bigr)\) です。まず、\(F, G\) の \(M\) 次以下の部分は二項係数（あるいは 疎な形式べき級数の pow） から \(O(M)\) 時間で計算できます。\(G\) が計算できれば、累積和を \(2\) 回とることで \(\frac{G}{(1-x)^2}\) の \(M\) 次以下が \(O(M)\) 時間で計算できます。

最後に、積の \(M\) 次の係数を答えます。積の係数を全部手に入れようと思うと畳み込みで \(O(M\log M)\) 時間かかりかねないですが、\([x^M]\) が欲しいだけなので、\(M+1\) 通りの係数の積の和として \(O(M)\) 時間で計算できます。

\([x^M]\) に限らず、\(M\) 次以下のすべての係数を \(O(M)\) 時間で計算することも可能です。

[多項式・形式的べき級数] 高速に計算できるものたち 「疎な場合の高速化 (2)」などを参考にしてください。

解答例（すべての係数を求める）：https://atcoder.jp/contests/abc276/submissions/36271360

さらに高速な解法。p-recursive 数列の \(N\) 項目が \(O(\sqrt N\log N)\) 時間で計算できることを使います。

\(F = \frac{(1+x)^N}{(1-x^3)^N(1-x)^2}\) は、対数微分を考えると \(1\) 階線形微分方程式の解となることが分かる（参考）ので、\(F\) の係数は p-recursive です。

解答例（2022/11/06 現在、最速実行時間）：https://atcoder.jp/contests/abc276/submissions/36285699