もしこの問題にタイプ \(1\) の操作 (追加) しかなければ、 \(dp\) [ 部分和 ] \(=\) { 場合の数 } のような DP をすることで解けます。
この解法を拡張して削除にも対応できないか考えます。

追加を行う際の DP の遷移は以下の通りです。

• \(i=K,K-1,\dots,x+1,x\) の順に以下の操作を行う。
  • \(dp[i]\) に \(dp[i-x]\) を加算する。

これを逆向きにすると削除についての正しい DP の遷移が導出できます。

• \(i=x,x+1,\dots,K-1,K\) の順に以下の操作を行う。
  • \(dp[i]\) から \(dp[i-x]\) を減算する。

また、 \(dp\) の添え字の範囲は \(0,1,\dots,K\) までしか保持する必要がありません。 ( \(dp[K+1]\) 以降の値は \(dp[K]\) 以前の値には影響しません )

実装例 (C++):

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

int dp[5005]={0};

int main(){
  int q,k;
  cin >> q >> k;
  dp[0]=1;
  while(q>0){
    q--;
    string s;
    int x;
    cin >> s >> x;
    if(s=="+"){
      for(int i=k;i>=x;i--){
        dp[i]+=dp[i-x];
        dp[i]%=mod;
      }
    }
    else{
      for(int i=x;i<=k;i++){
        dp[i]+=(mod-dp[i-x]);
        dp[i]%=mod;
      }
    }
    cout << dp[k] << "\n";
  }
  return 0;
}