AT_abc159_f [ABC159F] 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$ $\ldots$ $A_N$

输出格式

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

输入输出样例 #1

输入 #1

3 4
2 2 4

输出 #1

5

输入输出样例 #2

输入 #2

5 8
9 9 9 9 9

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

152

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 3000$
• $1 \leq S \leq 3000$
• $1 \leq A_i \leq 3000$

样例解释 1

可以分别计算如下，和为 $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)$ 这一种情况）

由 ChatGPT 4.1 翻译