Knapsack for All Segments

题目描述

给定一个由 $N$ 个整数 $A_1, A_2, \ldots, A_N$ 组成的序列以及一个正整数 $S$.
对于满足 $1\leq L \leq R \leq N$ 的整数对 $(L, R)$，定义 $f(L, R)$ 如下：

$f(L, R)$ 是满足 L \leq x_1 < x_2 < \cdots < x_k \leq R 且 $A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S$ 的整数组合 $(x_1, x_2, \ldots , x_k)$ 的个数。

求对所有满足 $1\leq L \leq R\leq N$ 的整数对 $(L, R)$ 的 $f(L, R)$ 之和。由于该和可能非常大，请对 $998244353$ 取模后输出。

输入格式

输入从标准输入按以下格式给出： $N$ $S$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出对 $f(L, R)$ 之和对 $998244353$ 取模后的结果。

3 4
2 2 4

5

5 8
9 9 9 9 9

0

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

152

提示

输入中的所有数值均为整数。 $1 \leq N \leq 3000$ $1 \leq S \leq 3000$ $1 \leq A_i \leq 3000$每一对的 $f(L, R)$ 值如下，总和为 $5$。

$f(1,1) = 0$ $f(1,2) = 1$（对应序列 $(1, 2)$） $f(1,3) = 2$（对应 $(1, 2)$ 和 $(3)$） $f(2,2) = 0$ $f(2,3) = 1$（对应 $(3)$） $f(3,3) = 1$（对应 $(3)$）

标签: AtCoder|abc159F

来源

AtCoder|abc159F