$O(K\log K)$ 解法を説明します。 $f_i(x) = (1+x)^i + x -1$ として $\sum_i 2^{K-1-i} f_i(x)^2$ を求めるものに帰着されます。
$f_i(x)^2 = (1+x)^{2i} + 2(x-1)(1+x)^i + (x-1)^2$ となるのでこれは $\sum_i 2^{K-1-i} (1+x)^{2i}, \sum_i 2^{K-1-i} (1+x)^i$ を求めるものに帰着できます。

\(\sum_i 2^{K-1-i} (1+x)^{2i}\) を考えます。 \(2^{-1} (1+x)^2 = \alpha\) としてこれは \(2^{K-1} (\alpha^0 + \alpha^1 + \dots + \alpha^{K-1}) = 2^{K-1} \frac{\alpha^K -1}{\alpha - 1}\) です。
よって多項式の pow や inv を用いることで \(O(K\log K)\) で計算できます。

\(\sum_i 2^{K-1-i} (1+x)^i\) についても同様に考えられます。よって全体で \(O(K \log K)\) で計算できます。