所有区间的背包

题目描述

给定长度为 $N$ 的整数数列 $A_1$, $A_2$, $\ldots$, $A_N$ 和正整数 $S$。

对于满足 $1\leq L \leq R \leq N$ 的整数对 $(L, R)$,定义 $f(L, R)$ 如下:

• 满足 $L \leq x_1 \lt x_2 \lt \cdots \lt 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$:

• $f(1,1) = 0$
• $f(1,2) = 1$((1, 2) 这 $1$ 个)
• $f(1,3) = 2$((1, 2) 和 (3) 这 $2$ 个)
• $f(2,2) = 0$
• $f(2,3) = 1$((3) 这 $1$ 个)
• $f(3,3) = 1$((3) 这 $1$ 个)

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$