\([x^Ny^M]f(x,y) =\)「総和 \(N\) かつ長さ \(M\) の素晴らしい整数列の個数」となるような \(2\) 変数母関数 \(f(x,y)\) を考えます。

包除原理を適用します。\(i\) が \(j\) 個連続しているとき、\((-1)^{j-1} x^{ij} y^{j}\) をかけます。\((-1)^{j-1}\) は、\(j-1\) 箇所で隣り合う要素が異なるを違反していることからです。これを \(i,j \ge 1\) を満たす全ての \(i,j\) について足し合わせたものを \(g(x,y)\) と置きます。すると、\(f(x,y) = \frac{1}{1-g(x,y)}\) となります。

\(g(x,y) = \sum_{i=1}^{\infty} \sum_{j=1}^{\infty} (-1)^{j-1}x^{ij}y^{j} = \sum_{i=1}^{\infty} \frac{x^iy}{1+x^iy}\) となります。ですが、このままだとそもそも \(f(x,y)\) を愚直に求めることが難しいです。

さて、ここで \([x^N] h(x)=\)「総和 \(N\) の素晴らしい整数列の長さの総和」となるような母関数 \(h(x)\) を考えます。すると、\(h(x)\) は \(\frac{d}{dy} f(x,y)\) に \(y=1\) を代入したものとなります。

\(\frac{d}{dy} f(x,y)=\frac{d}{dy} \frac{1}{1-g(x,y)} = \frac{\frac{d}{dy} (g(x,y) - 1)}{(1-g(x,y))^2}\) となります。

\(\frac{d}{dy} (g(x,y)-1)\) を考えます。これは、\(\frac{d}{dy} \frac{x^iy}{1+x^iy} = \frac{x^i}{(1+x^iy)^2}\) より、\(\sum_{i=1}^{\infty} \frac{x^{i}}{(1+x^iy)^2}\) です。

よって、ここに \(y=1\) を代入すればよいため、\(h(x) = \displaystyle \frac{\sum_{i=1}^{\infty} \frac{x^{i}}{(1+x^i)^2}}{\left(1-\sum_{i=1}^{\infty} \frac{x^i}{1+x^i}\right)^2}\) となります。

分子、分母の項をそれぞれ展開しても、次数 \(N\) 以下の部分は \(\mathrm{O}(N\log N)\) 項しかないため愚直に求めることが出来ます。そして、多項式の逆元を \(\mathrm{O}(N\log N)\) ですることでこの問題を \(\mathrm{O}(N\log N)\) で解くことが出来ます。これは十分高速です。

多項式の逆元の求め方については、ABC260-Ex の解説 に書かれています。