PCTprobability さんのユーザー解説 における \(Q_i=[x^0]f(x)^i\) について，\(Q_0,\dots,Q_H\) を \(O(HW(\log HW+(\log H)^2))\) で列挙できます．

\(f(x)\) は \(-(W-2)\) 次から \(W-2\) 次までの項しか持たないので，\(HW\lt N\) となる整数 \(N\) を固定すると \(Q_i=[x^0]f(x)^i\bmod(1-x^N)\) です．

以下 \(N\) は \(HW\lt N\) を満たす \(2\) べきの整数のうち最小のものとします．本問題の制約下では \(HW\leq 240000\) より \(N\leq 2^{18}\) です．

長さ \(N\) の離散フーリエ変換を考えれば，\(1\) の原始 \(N\) 乗根 \(\zeta\) に対し次が成り立ちます． \[[x^0]f(x)^i\bmod(1-x^N)=\frac{1}{N}\sum_{j=0}^{N-1}f(\zeta^{-j})^i\]

\(f(\zeta^{-j}),0\leq j\lt N\) は離散フーリエ変換によって \(O(N\log N)=O(HW\log HW)\) で列挙できます． あとは次の形式的冪級数の \(H\) 次までが計算できればよいです． \[\frac{1}{N}\sum_{j=0}^{N-1}\frac{1}{1-f(\zeta^j)x}\]

これは分割統治で \(O(N(\log N)^2)=O(HW(\log HW)^2)\) で計算できます（参考：[多項式・形式的べき級数] 高速に計算できるものたち - maspyのHP）が，さらに計算の過程で \(H\) 次より上の項は逐次切り捨てることで計算量が \(O(N(\log H)^2)=O(HW(\log H)^2)\) になることが確認できます．

従って \(Q_0,\dots,Q_H\) を \(O(HW(\log HW+(\log H)^2))\) で列挙できることがわかりました．