atcoder abc 159：F - Knapsack for All Segments（思维 + 贡献 + dp）

---

有一个 $n^3$n3 的朴素做法，对每个区间 进行 dp，显然是通过不了的，且转移复杂度为 O(1)，没有优化的空间，得考虑从其它角度切入这题。

对于某个解，最左边的数字的下标为 $x$x，最右边的数字的下标为 $y$y，这组解对答案的贡献为：$x * (n - y + 1)$x∗(n−y+1)，考虑枚举每个数字作为一组解的最右边的点，对于第 i 个数字，需要知道前 $i-1$i−1个数字，每种权值和为 $s - a[i]$s−a[i] 的方案的最左边的数字的下标和，这个可以 dp 得到，设 $dp[i][v]$dp[i][v] 表示前 $i$i 个数字，权值和为 v 的各种方案中，最左边的数字的下标和，显然 $dp[i][v] = dp[i - 1][v] + dp[i - 1][v - a[i]]$dp[i][v]=dp[i−1][v]+dp[i−1][v−a[i]]，当 $v = a[i]$v=a[i] 时，$dp[i][a[i]] += i$dp[i][a[i]]+=i

第一维可以滚动，则每个数字作为最右边的数时对答案的贡献为：$(n - i + 1) * dp[s - a[i]]$(n−i+1)∗dp[s−a[i]]

注意特判转移时， $s = a[i]$s=a[i] 的情况，这时最左最右均为 i

---

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 10;
const int mod = 998244353;
typedef long long ll;
#define lowbit(i) (i & (-i))
ll sum[maxn];
int n,m,k,a[maxn],s,dp[maxn];
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 (s > a[i]) ans = (ans + 1ll * dp[s - a[i]] * (n - i + 1)) % mod;
		else if (s == a[i]) ans = (ans + 1ll * i * (n - i + 1)) % mod;
		for (int j = s; j >= a[i]; j--)
			dp[j] = (dp[j] + dp[j - a[i]]) % mod;
		dp[a[i]] = (dp[a[i]] + i) % mod;
	}
	printf("%d\n",ans);
}