← 返回题目列表

AtCoder · stpc2025_2_b

B. 剧烈旋转

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

配点 : 100 点

問題文

1,2,\ldots ,N 有 N 行李件左右并排放置。一、行李 它被放置在第 i 从左起 代表 i 个位置。此外,每件行李都有规定的重量,并且 i 的权重是 A_i 。

您对此包列执行以下一系列操作。 0 您可以随意执行多次。 小于或等于

  1. 1 \le L \lt R \le N 的一组整数 (L,R) 从左起 第 L,L+1, \ldots ,R 件行李的总重量为 K 类似的东西 循环将第 1 选择一项。
  2. 从左起 从第 L,L+1, \ldots ,R 个包向左移动。也就是说,从左边开始 放置在 L 位置的行李是从左边开始的。 从左侧开始,使其处于第 R 位置。 放置在 L+1,\ldots ,R 位置的行李是从左边开始的。 移动行李,使其位于第 L,\ldots ,R-1 位置。

计算所有操作完成后包裹可能的排列方式的数量。 998244353 后求余数。

制約

  • 所有输入均为整数
  • 2 \le N \le 2 \times 10^5
  • 1 \le K \le 10^{14}
  • 1 \le A_i \le 10^8

入力

输入按以下格式给出。

N K
A_1 A_2 \ldots A_N

出力

打印答案。 来自


入力例 1

4 7
1 2 2 3

出力例 1

12

初始状态下,从左起 第 2,3,4 件行李的总重量为 2+2+3=7 \ge K=7 所以作为第一个操作 您可以选择 (L,R)=(2,4) 。执行此操作后,包裹编号将从左到右编号。 1,3,4,2 。 对于

所有操作完成后整理行李的可能方式 12 如下。

请注意,即使包裹的重量相同,包裹也会根据数量进行区分。在这种情况下,包裹编号是从左到右依次排列的。 1,2,3,4 排列1,3,2,4 被视为不同的排列。


入力例 2

2 100
1 1

出力例 2

1

操作是 1 您甚至可能无法执行此操作一次。 请回答除以


入力例 3

20 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

出力例 3

401576539

998244353 后的余数。