\(F\) と \(G\) は線形漸化式を持つので、母関数はそれぞれ \(P(x) / Q(x), R(x) / S(x)\) と表されます。ただし \(P, Q, R, S\) は何らかの多項式です。 ここで、\(G\) の \(0\) 項目から \(K\) 項目までを取り出した数列の母関数は多項式となり、何らかの多項式 \(T\) を用いて \((R(x) - x^{K+1} T(x)) / S(x)\) と表されます。これは、\(G\) の第 \(K + 1\) 項以降を取り出した数列もまた \(G\) と同じ線形漸化式を満たすからです。 \(T\) の計算は \(O(M \log(M) \log(K))\) で行うことができます。 参考: https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0%EF%BC%88%EF%BC%93%EF%BC%89%E7%B7%9A%E5%BD%A2%E6%BC%B8%E5%8C%96%E5%BC%8F%E3%81%A8%E5%BD%A2%E5%BC%8F#toc9

求める値は \(G\) の \(0\) 項目から \(K\) 項目を反転して \(F\) と畳み込めば得られるので、式で表すと以下のようになります。

\[ [x ^ 0] \frac{P(x)}{Q(x)} \frac{R(x^{-1}) - x^{-(K+1)} T(x^{-1})}{S(x^{-1})} \]

ただし、計算は形式的ローラン級数で行っています。 \(S\) の次数を \(n\) として分子と分母に \(x^ n\) を掛け、更に展開して整理すると以下のようになります。

\[ [x ^ 0] \frac{P(x)}{Q(x)} \frac{x^n R(x^{-1})}{x^n S(x^{-1})} - [x ^ {K+1}] \frac{P(x)}{Q(x)} \frac{ x^nT(x^{-1})}{x^nS(x^{-1})} \]

\(x^n S(x^{-1})\) は定数項が \(0\) でない多項式になります。 \(x^n R(x^{-1})\) は \(1\) 次以上の項しか持たないので、第 \(1\) 項は \(0\) です。第 \(2\) 項は \(O((N+M) \log(N+M) \log(K))\) で計算できます。