题目描述
求 (A) 的所有连续子段的 "子序列中元素的和等于 (S) 个数" 的和。
正解
求一个连续子段等于 (S) 的个数，可以用背包做到 (O(n^2))。
但要对于每一个区间做一次背包，复杂度实在过不去。
考虑一个子序列在 (A) 中产生的贡献（所有连续子段中的出现次数）。
子序列左端点是 (l)，右端点是 (r) 的话，那么产生的贡献就是 (l imes (n - r + 1))。
发现这个贡献只与左右端点有关，那么就再做背包的时候魔改一下。
具体是这样实现的：
加入背包的时候，
-
如果当前没有放元素，那么乘上一个 (l) 的系数 （即加上 (l) 而不是加 1）。（左端点的贡献）
-
如果放入当前元素背包满了，那么对答案产生 (f_s imes (n - r + 1)) 的贡献。（右端点的贡献）
-
否则就按普通背包做就行了。
代码
#include <bits/stdc++.h>
#define N 3005
using namespace std;
const int mod = 998244353;
int n, S;
int a[N], f[N];
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) {
if(a[i] > S) continue;
else if(a[i] == S) {
ans = (ans + 1LL * i * (n - i + 1)) % mod;
} else {
ans = (ans + 1LL * f[S - a[i]] * (n - i + 1)) % mod;
for(int j = S; j > a[i]; --j)
(f[j] += f[j - a[i]]) %= mod;
f[a[i]] = (f[a[i]] + i) % mod;
}
}
printf("%d
", ans);
return 0;
}