\(\displaystyle f(x)=1+x+x^2+x^3+\dots=\sum\limits_{i=0}^{\infty}x^i, g(x)=x+x^2+x^4+x^5+x^7+x^8+\dots=\sum\limits_{i \geq 0, i \bmod 3 \neq 0} x^i\) とおくと、答えは \([x^M]f(x)^2g(x)^{N-1}\)と表されます。(類題: maspy さん記事 問題 14・15)

\(\displaystyle f(x)=\frac{1}{1-x}, g(x)=\frac{x+x^2}{1-x^3}\) であることを用いて、これを式変形します。

\(\displaystyle [x^M]f(x)^2g(x)^{N-1}\)

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

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

\(\displaystyle =[x^M]\frac{x^{N-1}(1+x+x^2)^2(1+x)^{N-1}}{(1-x^3)^{N+1}}\) (分母と分子に \((1+x+x^2)^2\) を掛けた)

\(\displaystyle =[x^M]\left(x^{N-1}(1+x+x^2)^2(1+x)^{N-1}\right)\left((1-x^3)^{-(N+1)}\right)\)

\((1+x)^{N-1}\) は二項定理より \(\displaystyle \sum\limits_{i=0}^{N-1} {}_{N-1} C_i x^i\) となります。これに \(x^{N-1}(1+x+x^2)^2=x^{N-1}(1+2x+3x^2+2x^3+x^4)\) を掛けた多項式の係数は \(O(N)\) 時間で得ることができます。

\((1-x^3)^{-(N+1)}\) は負の二項定理より \(\displaystyle \sum\limits_{i=0}^{\infty} {}_{i+N}C_N x^{3i}\) となり、答えに影響する \(M\) 次以下の係数のみ求めればよく、これは \(O(N+M)\) 時間で得ることができます。

よって、この問題は \(O(N+M)\) 時間で解くことができます。

実装例: https://atcoder.jp/contests/abc276/submissions/36264066