题目描述

难度分:$1876$

输入$n(1 \leq n \leq 3000)$、$s(1 \leq s \leq 3000)$和长为$n$的数组$a(1 \leq a[i] \leq 3000)$。

• 定义$f(L,R)$等于：在子数组$a[L],a[L+1],…,a[R]$中，元素和恰好等于$s$的子序列的个数。

输出所有$f(L,R)$的和，其中$0 \leq L \leq R \leq n$。

模$998244353$。

输入样例$1$

3 4
2 2 4

输出样例$1$

5

输入样例$2$

5 8
9 9 9 9 9

输出样例$2$

0

输入样例$3$

10 10
3 1 4 1 5 9 2 6 5 3

输出样例$3$

152

算法

01背包

状态定义

定义$f[i][j]$表示子数组右端点为$i$（左端点任意），子序列和为$j$的方案数。显然，本题的答案就是$f[0][s]+f[1][s]+…+f[n-1][s]$。

状态转移

每个元素$a[i]$都可以选或者不选，因此状态转移方程为

$f[i][j] = f[i-1][j] + f[i-1][j-a[i]]$

这里需要注意一下$s=0$时的初始值$f[i][0] = i$。如$f[2][0]$表示子数组$[2,2]$中有$1$个子序列（空序列）和为$0$，子数组 $[1,2]$中有$1$个子序列（空序列）和为$0$，所以$f[2][0]=2$。

复杂度分析

时间复杂度

整个算法是一个01背包的流程，由于$S$和$N$是同一个规模的，因此时间复杂度为$O(n^2)$。

空间复杂度

利用内层循环倒序遍历优化掉了第一维，额外空间复杂度就是$f$数组的大小，为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3010, MOD = 998244353;
int f[N], a[N], n, s;

int main() {
    scanf("%d%d", &n, &s);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        f[0]++;
        for(int j = s; j >= a[i]; j--) {
            f[j] = (f[j] + f[j - a[i]]) % MOD;
        }
        ans = (ans + f[s]) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}