\(O(N\log N + \log K)\) 時間になるので一応書いておきます．\(N\) 次以下の多項式 \(A(x), B(x)\) について

\[\frac{A(x)}{(1-x)^{N+1}}+\frac{B(x)}{(1-2x)^{N+1}}\]

が \(2N+1\) 次まで求まってるとします．通分すれば

\[f(x)=A(x)(1-2x)^{N+1}+B(x)(1-x)^{N+1}\]

が求まっています．\(f\) が与えられたとして，\(A, B\) を得ることが目標です．\(A\) は

\[A(x)(1-2x)^{N+1}\equiv f(x)\pmod{(1-x)^{N+1}}\]

の解として求まります．この解は \((1-x) ^ {N+1}\) を法として一意ですが，\(\deg A\leq N\) だと一意です．合同式を解く方法ですが，この場合は \(y=(1-x)\) という変数変換をするのが簡単です．\(y ^ {N+1}\) を法とする計算に帰着されますが，これは単に形式的べき級数逆元の \(N\) 次以下を使って計算できます．

以上のように \(A(x),B(x)\) を復元したら，負の二項定理から \([x^K]\) 取得が \(O(N+\log K)\) 時間でできます．