2023牛客暑假多校第四场（补题向题解：J）

终于有时间来慢慢补补题了

J Qu’est-ce Que C’est?

作为队内的dp手，赛时想了好久，等学弟学妹都出了还是不会，羞愧，还好最终队友做出来了。
链接J Qu’est-ce Que C’est?

题意

长度为 $n$ 的数组 $a$，每个数的取值范围 $a_i=[-m,m]$，问所有满足长度 $>1$ 的子段的和为非负数的数组可能的数量。$1\le n,m\le 5000$。

以下题解，仅参考懵哥的状态定义，具体解题过程优化和代码都是博主自己琢磨的。

法一思路

dp状态定义 $f[i][j]:$ 前 $i$ 个数，最小后缀和为 $j$ 的方案数 $j=[-5000,5000]$。因为是最小后缀和，那么如果有后缀 $<-5000$ 的说明至少是两个数以上的和为负数，与题意不符是不合法的方案，所以数组大小开到 $[0,10000]$ 即可（离散化后）。

我们先不管时间复杂度，根据dp定义先敲个状态转移出来，代码如下：

#include 
using namespace std;

#define ll long long

const int N = 5010, mod = 998244353;

int f[N][N * 2]; // 前i个数，最小后缀和为j的方案数 j = [-5000, 5000]

void add(int& a, int b){
    a = (a + b) % mod;
}
int main(){
    int n, m;
    cin >> n >> m;

    f[0][2 * m] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = -m; j <= m; j ++){ // 枚举最小后缀
            for(int k = m; k >= -m; k --){ // 枚举当前a_i选哪个数
                if(j + k < 0) break;
                add(f[i][min(j + k, k) + m], f[i - 1][j + m]);
            }
        }
        
    }
    
    int ans = 0;
    for(int i = -m; i <= m; i ++){
        add(ans, f[n][i + m]);
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

时间复杂度为 $O(n^3)$，我们观察一下代码如何优化，发现会有大量连续的 $k$，$f[i][\min (j+k,k)]$ 加的是同一个状态 $f[i-1][j]$。那么经典优化方案不就来了吗，差分前缀和优化。

以下分情况讨论：
因为是 $\min (j+k,k)$

1. $j$ 是非正数
   无论当前 $k$ 选什么，$j+k\le k$，所以状态一定是转移到 $j+k$，所以对于一个非正数的 $j$ 可转移的范围就是 $0\sim j+m$。

// 区间 [l, r] + val  f_l + val  f_{r + 1} + val
for(int j = -m; j <= 0; j ++){
    f[i][m] = (f[i][m] + f[i - 1][j + m]) % mod;// 差分 +
    f[i][m + j + m + 1] = (f[i][m + j + m + 1] + mod - f[i - 1][j + m]) % mod;// 差分 -
}
1
2
3
4
5

2. $j$ 是正数
   同理无论当前 $k$ 选什么，$k\le j+k$，所以状态一定是转移到 $k$，所以对于一个正数 $j$，可以转移的范围就是 $-j\sim m$。

for(int j = 1; j <= m; j ++){
    f[i][-j + m] = (f[i][-j + m] + f[i - 1][j + m]) % mod;
    f[i][m + m + 1] = (f[i][m + m + 1] + mod - f[i - 1][j + m]) % mod;
}
1
2
3
4

法一完整代码

#include 
using namespace std;

#define ll long long

const int N = 5010, mod = 998244353;

int f[N][N * 2]; // 前i个数，最小后缀和为j的方案数 j = [-5000, 5000]

void add(int& a, int b){
    a = (a + b) % mod;
}
int main(){
    int n, m;
    cin >> n >> m;

    f[0][2 * m] = 1;
    for(int i = 1; i <= n; i ++){
        /*
        for(int j = -m; j <= m; j ++){
            for(int k = m; k >= -m; k --){
                if(j + k < 0) break;
                add(f[i][min(j + k, k) + m], f[i - 1][j + m]);
            }
        }
        */
        
        // 考虑差分前缀和优化
        // j 是 负数 k 是正数 f[i][j + k + m] 从0 ~ m + j
        // j 是 正数 k 是负数/正数 f[i][k + m] 从-j ~ m

        for(int j = -m; j <= 0; j ++){
            f[i][m] = (f[i][m] + f[i - 1][j + m]) % mod; // 差分 +
            f[i][m + j + m + 1] = (f[i][m + j + m + 1] + mod - f[i - 1][j + m]) % mod; // 差分 -
        }
        for(int j = 1; j <= m; j ++){
            f[i][-j + m] = (f[i][-j + m] + f[i - 1][j + m]) % mod;
            f[i][m + m + 1] = (f[i][m + m + 1] + mod - f[i - 1][j + m]) % mod;
        }
        for(int j = -m + 1; j <= m; j ++){ // 前缀和
            f[i][j + m] = (f[i][j + m] + f[i][j + m - 1]) % mod;
        }
    }

    int ans = 0;
    for(int i = -m; i <= m; i ++){
        add(ans, f[n][i + m]);
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

法二思路

首先先说说博主自己解题时卡在什么地方，我当时认为dp必须维护 $a_{i-1}$ 和 $a_{i-2}$ 位置上的数是什么，才能确定当前选择的 $a_i$ 的选择是否合法，这样的时空复杂度都达到了 $n^3$，而且也没有能发现优化的点。而不得不说这个思路也很妙，仅仅一个点就将时空都缩减了一维，可以不用维护 $a_{i-2}$ 的情况。

你可能会和我一样疑惑，如果不维护 $a_{i-2}$ 若 $a_{i-2}+a_{i-1}+a_i<0$ 的情况如何排除，我们考虑一下合法序列的情况：对于一个合法序列，肯定不会出现两个连续的负数，即一个负数的后继肯定是正数。 所以dp方程的第二维维护的就是当前节点的数值大小，因为负数是和正数绑定的，我们将一个负数和其后继的正数当做一个数来记录，转移时直接从 $d{p}_{i-1}$ 转移到 $d{p}_{i+1}$。

$f[i][j]：$ 前 $i$ 个数，第 $i$ 个数大小为 $j$ 的合法方案数。

老样子，我们不考虑优化先写个暴力转移出来

#include 
using namespace std;

const int N = 5010, mod = 998244353;

int f[N][N * 2], pre[N * 2];

void add(int& a, int b){
    a = (a + b) % mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    f[0][m] = 1; // 初始化一个最大的数作为第0个数
    
    int ans = 0;
	
    // 暴力转移
    for(int i = 1; i <= n; i ++){
        
        // 枚举前一个数的值j，因为但凡出现负数我们就会将其与一个正数合并为非负数一起维护，所以不需要离散化和枚举负数
        for(int j = 0; j <= m; j ++){ 
            for(int k = -j; k <= 0; k ++){ // 枚举当前选负数
            	if(i == n) add(ans, f[i - 1][j]); // 最后一个数不用和正数绑定，单独计算
                else{
                    for(int p = -k; p <= m; p ++){ // 枚举与负数绑定一起选的正数
                        add(f[i + 1][k + p], f[i - 1][j]);
                    }
                }
            }
            for(int k = 1; k <= m; k ++){ // 枚举当前选的正数
                add(f[i][k], f[i - 1][j]);
            }   
        }
    }
    for(int i = 0; i <= m; i ++){
        add(ans, f[n][i]);
    }
    cout << ans << "\n"; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

先从简单的开始优化，看当前选的数 $k$ 为正数的情况，我们发现dp定义中，将所有负数和正数绑定在一起，所以dp状态中所有数都是正数。也就是所有的 $j$ 都可以转移到 $k$，我们直接记录一下前缀和，枚举 $k$ 全部加上即可，代码如下：

for(int i = 1; i <= n; i ++){
    pre[1] = f[i - 1][0];
    for(int j = 1; j <= m; j ++){ // 前缀和
        pre[j + 1] = (pre[j] + f[i - 1][j]) % mod;
    }
    for(int k = 1; k <= m; k ++){ // 枚举当前选的正数
        f[i][k] = (f[i][k] + pre[m + 1]) % mod; // 正数之间任意转移直接将前缀和全部加上
    }
}
1
2
3
4
5
6
7
8
9

再考虑当前 $k$ 为负数需要和正数绑定的情况。若当前选负数，那么该负数与 前一个正数，后一个正数的和都不能为负，所以直接枚举当前选哪个负数。若当前选的负数为 $k$，前一个正数 $j\ge -k$ 且 后一个正数 $p\ge -k$，也就是说 $j=[-k,m]$ 可以转移到 $p=[-k,m]$。即：

$f[i+1][0\sim k+m]+{\sum }_{j=-k}^{m}f[i-1][j]$。

$f[i-1]$ 已经用前缀和维护好了，而 $f[i+1]$ 这种经典的连续一段加同一个数的转移是否能想到优化方法，没错就是差分前缀和，具体见代码。

法二完整代码

#include 
using namespace std;

const int N = 5010, mod = 998244353;

int f[N][N * 2], pre[N * 2];

void add(int& a, int b){
    a = (a + b) % mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    f[0][m] = 1; // 初始化一个最大的数作为第0个数
    
    int ans = 0;
    // 优化
    for(int i = 1; i <= n; i ++){
        
        pre[1] = f[i - 1][0];
        for(int j = 1; j <= m; j ++){ // 前缀和
            pre[j + 1] = (pre[j] + f[i - 1][j]) % mod;
        }

        // 考虑到若当前选负数，那么该负数和 前一个正数 和 后一个正数的和都不能为负，所以直接枚举当前选哪个负数
        for(int k = -m; k <= 0; k ++){
            int sum = (pre[m + 1] + mod - pre[-k]) % mod; // f[i - 1] 能转移的前缀和

            if(i < n){ // 前一个数和后一个数都至少要 >= -k, 转移范围为[i - 1][-k, m](前缀和) -> [i + 1][0, k + m](差分前缀和)
                f[i + 1][0] = (f[i + 1][0] + sum) % mod; // 差分 +
                f[i + 1][k + m + 1] = (f[i + 1][k + m + 1] + mod - sum) % mod; // 差分 -
            }
            else{// 最后一个数可以直接选负数
                ans = (ans + sum) % mod; // 转移范围为 f[i - 1][-k ~ m] -> f[i][k] 直接加在ans上
            }
        }

        for(int j = 1; j <= m; j ++){// 前缀和维护差分
            f[i + 1][j] = (f[i + 1][j] + f[i + 1][j - 1]) % mod; 
        }

        for(int k = 1; k <= m; k ++){ // 枚举当前选的正数
            f[i][k] = (f[i][k] + pre[m + 1]) % mod; // 正数之间任意转移直接将前缀和全部加上
        }
    }


    for(int i = 0; i <= m; i ++){
        add(ans, f[n][i]);
    }
    cout << ans << "\n"; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56