J题解

J.Qu'est-ce Que C'est?

题意

问所有仅由 $-m\sim m-m\backslash sim\; m$ 之间的数组成的长度为 $nn$ 整数序列中，任意长度大于等于 $22$ 的区间的和都大于 $00$ 的整数序列数量有多少。

解题思路

考虑使用动态规划，设 $dp[i][j]dp[i][j]$ 为前 $ii$ 个数最小后缀和为 $jj$ 的整数序列数量，设整数序列为 $aa$，最小后缀和指对于所有 $k(1\le k\le j)k(1\backslash le\; k\backslash le\; j)$ 的 ${}_{k=1}^j{\sum }_{x=k}^j{a}_x\backslash min\_\{k=1\}^j\{\backslash sum\_\{x=k\}^ja\_x\}$。

1. 当 $j\ge 0j\backslash ge\; 0$ 时，第 $ii$ 个位置的最小后缀和为 $jj$，那么我们可以加上所有长度为 $i-1i-1$ 的最小后缀和大于等于 $j-mj-m$ 的整数序列数量，假如第 $i-1i-1$ 个位置的最小后缀和小于 $j-mj-m$ 的话第 $ii$ 个位置的最小后缀和是不可能为 $jj$ 的，并且这些情况也包括了第 $ii$ 个位置最小后缀和为 $jj$ 的所有情况，状态转移方程为：$dp[i][j]={\sum }_{k=j-m}^{m}dp[i-1][k]dp[i][j]=\backslash sum\_\{k=j-m\}^mdp[i-1][k]$。
2. 当 时，所有长度为 $ii$ 的最小后缀和为 $jj$ 的整数序列的第 $ii$ 个位置一定是 $jj$，因为假如是后缀长度大于等于 $22$ 的和为 $jj$，$jj$ 又是小于 $00$ 的，和题意不符合，所以只能加上长度为 $i-1i-1$ 的最小后缀和大于 $-j-j$ 的整数序列数量。

AC_Code

//
// Created by liuhao.
//

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const  int mod=998244353;
signed main()
{
 	ios;
    int n,m;
    cin>>n>>m;
    vector<vector<int>>dp(n+1,vector<int>(2*m+2,0)),sum(n+1,vector<int>(2*m+2,0));
    for(int i=2*m;i>=0;i--)
    {
        dp[1][i]=1;
        sum[1][i]=sum[1][i+1]+1;
    }
    for(int i=2;i<=n;i++)
    {
        for (int j = -m; j <= m; j++) {
            if(j<0)dp[i][j+m]=sum[i-1][-j+m];
            else {
                dp[i][j + m] = sum[i - 1][j - m + m];
            }
        }
        for (int j = m; j >=-m ; j--) {
            sum[i][j+m]=sum[i][j+1+m]+dp[i][j+m];
            sum[i][j+m]%=mod;
        }
    }
    cout<<sum[n][0];
    return 0;
}