本質的には physics0523さんによる解説 と同一です。

今回の問題は、形式的冪級数を用いて解釈することも可能です。

今回の問題は、\(f(x)=1\) からはじめ、以下の操作を \(Q\) 回繰り返し、各操作後に \(x^K\) の係数を出力すれば良いです。（\(x\) が混在するため、以下入力で与えられる整数は \(d\) と表記します）

• + のとき： \(f(x)\) に \(1+x^d\) を掛ける
• - のとき： \(f(x)\) を \(1+x^d\) で割る

これらの操作は、 \(f\) の \(0\) 次の項から \(K\) 次の項までを管理することで \(\mathrm{O}(K)\) で可能です。

これらの掛け算、割り算をよく考えると、公式解説の DP の更新と同一であることが分かります。