AT_abc321_f 题解

# 思路

简单动态规划，$dp_i$ 指当前操作后取和为 $i$ 的球的方案数，每次输出 $dp_K$ 即可。

需要注意的是对于每次 `+ x` 操作，计算 $dp$ 数组时要倒着循环。

时间复杂度：$O(QK)$。

# 代码

```cpp
#include<bits/stdc++.h>
using namespace std;
long long dp[5010];
int main(){
long long q,k; scanf("%lld %lld",&q,&k);
dp[0]=1;
for(int i=1;i<=q;i++){
char c;
long long x;
scanf("%c",&c);
while(c!='+'&&c!='-')scanf("%c",&c);
scanf("%lld",&x);
if(c=='+')
for(long long j=5004;j>=x;j--)
dp[j]=(dp[j]+dp[j-x]+998244353)%998244353;
else
for(long long j=x;j<=5004;j++)
dp[j]=(dp[j]-dp[j-x]+998244353)%998244353;
printf("%lld\n",dp[k]);
}
return 0;
}
```