https://atcoder.jp/contests/utpc2023/editorial/9599 と同様の考察により、\(f_K(x)=(1+x)^K+x-1\) としたとき \(g_K(x) = \sum_{i=0}^{K-1} 2^{K-1-i}f_i(x)^2+2^Kx+(2^K-1)(-x^2+x)\) を求めればよいです。

\( \sum_{i=0}^{K-1} 2^{K-1-i}f_i(x)^2\) を求められればよく、これを \(h(x)\) とおくと、\(h(x-1)= \sum_{i=0}^{K-1} 2^{K-1-i}f_i(x-1)^2=\sum_{i=0}^{K-1} 2^{K-1-i} (x^K+x-2)^2\) であり、これは \(\mathrm{O}(K)\) 時間で計算できます。これに Polynomial Taylor Shift を適用すると、\(h(x)\) を \(\mathrm{O}(K \log K)\) 時間で計算できます。