2023年icpc江西省赛-D

题目链接：https://codeforces.com/gym/104385/problem/D

我的三维空间dp思路：设dp[i][j][k][0/1]表示前i个操作已经弹出了j个值，并且当前有k个连续弹出的数，当前序列合不合法的方案数，这样的dp优化成二维空间的，所以舍弃。

正解思路：最朴素的想法是三维暴力dp，设dp[i][j][0/1]表示前i个push了，且弹出了j个，当前序列合不合法的方案数。然后发现可以前缀和处理转移方程。然后发现转移时可以前缀和优化掉一层循环。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3100,mod = 998244353;
long long dp[N][N][2];
int main(){
    int n,m;
    cin>>n>>m;
    dp[0][0][0] = 1;
    for (int i=1;i<=n;i++){
        for (int j=0;j<=i;j++){
            if (j>=m){
                dp[i][j][0] = (dp[i-1][j][0]-dp[i-1][j-m][0]+mod)%mod;
                dp[i][j][1] = (dp[i-1][j-m][0]+dp[i-1][j][1])%mod;
            }else{
                dp[i][j][0] = dp[i-1][j][0];
            }
        }
        for (int j=1;j<=i;j++) dp[i][j][0] = (dp[i][j-1][0]+dp[i][j][0])%mod;
        for (int j=1;j<=i;j++) dp[i][j][1] = (dp[i][j-1][1]+dp[i][j][1])%mod;
    }
    cout<<dp[n][n][1]<<'\n';
}