問題概要
Muliset に対する部分和問題に，追加と削除クエリを与えたもの． 俗に戻すDPと呼ばれる．
解法
(0) まず，multiset が固定されている場合を考える． これは普通の部分和DP. とくに，配列を 1次元にした inplace DP で考えると， 今回の問題に応用するときに楽．
(1) 次に，multiset に1つ元 \(x\) を追加または削除することを考える． 簡単な追加の方を考える． (0)の考えを用いると，
\(dfor \ i \in [x,k]\)
\(dp_{i} += dp_{i-x}\)
\(dp_{i} += dp_{i-x}\)
という処理をしている．
削除の方も同様に，
\(for \ i \in [x,k]\) \(dp_{i} -= dp_{i-x}\)
と出来る．for の順番が反転することと，\(+\) と \(-\) も反転している．
注意
多項式を使った数え上げを考えると，操作が可換であることが用意に分かる． \(t\) に関する多項式とする． \(x\) を mutiset に追加することは，多項式に \(1+t^{x}\) を掛けることに対応して， \(x\) を mutiset から削除することは，多項式に \(1+t^{x}\) で割ることに対応する． 積と割り算は共に可換．
また，Multiset から元を選んで部分和を作るとき，一つの元に対して 1回しか使えないというルールなので \(dfor \ i \in [x,k]\) \(dp_{i} += dp_{i-x}\) としている． もし，1つの元を何度でも使えるというルールなら， \(for\) になる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll q,k; cin >> q >> k;
dp[0] = 1;
rep(qi,q){
char c; ll x; cin >> c >> x;
if(c == '+'){
for(int i = k; i >= x; i--){
dp[i] += dp[i-x];
}
}else{
for(int i = x; i <= k; i++){
dp[i] -= dp[i-x];
}
}
cout << dp[k].val() << endl;
}
return 0;
}
