追記：この解法は嘘解法（特定のテストケースに対して正しくない答えを返す解法）であることが判明しました。以下の解説は参考にしないようお願いいたします。詳細についてはrsk0315さんの解説をご参照ください。

公式解説にもある通り、\(f_1\circ f_2\circ\cdots\circ f_i\)の逆関数を求めるためには\(x^i\)での除算が必要となり、\(x^i\)が小さいときにこの除算を十分な精度で行うのは難しいです。

そこで、\((f_1\circ f_2\circ\cdots\circ f_i)(0)\)ではなく\(h_i:=(f_i\circ f_{i+1}\circ\cdots\circ f_N)(0)\)を各\(1\leq i\leq N\)について事前に求めておくことにします。

すると、

\(\begin{aligned}(f_l\circ f_{l+1}\circ\cdots\circ f_{r})(0)&=(f_l\circ f_{l+1}\circ\cdots\circ f_{N})(0)-(f_{r+1}\circ f_{r+2}\circ\cdots\circ f_{N})(0)\times x^{r-l+1}\\&=h_l-h_{r+1}\times x^{r-l+1}\end{aligned}\)

となるため、除算なしで\((f_l\circ f_{l+1}\circ\cdots\circ f_{r})(0)\)の値を求めることができます。

時間計算量は\(O(N+Q)\)です。

実装例（C++）

実装例（PyPy）