← 返回题目列表

AtCoder · abc159_f

F. 适用于所有细分市场的背包

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给出了一系列 N 整数 A_1, A_2, \ldots, A_N 和一个正整数 S.
对于一对整数 (L, R) 这样 1\leq L \leq R \leq N,让我们定义 f(L, R) 如下:

  • f(L, R) 是整数序列的数量 (x_1, x_2, \ldots , x_k) 这样 L \leq x_1 < x_2 < \cdots < x_k \leq R 和 A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

求总和 f(L, R) 所有整数对 (L, R) 这样 1\leq L \leq R\leq N。由于这个和可能是巨大的,所以打印它的模 998244353.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 3000
  • 1 \leq S \leq 3000
  • 1 \leq A_i \leq 3000

输入

输入由标准输入按以下格式给出:

N S
A_1 A_2 ... A_N

输出

打印总和 f(L, R),模数 998244353.


示例输入 1

3 4
2 2 4

示例输出 1

5

的值 每对的 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))

示例输入 2

5 8
9 9 9 9 9

示例输出 2

0

示例输入 3

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

示例输出 3

152