#3739. 「LNOI2022」盒

题目描述

有 $n$ 个不同的盒子排成一排。在初始状态下，第 $i$ 个盒子放有 $a_i$ 个货物，总货物数量为 $S = \sum_{i = 1}^{n} a_i$ 。对于非负整数数组 $(b_1, b_2, \ldots, b_n)$ 满足 $\sum_{i = 1}^{n} b_i = S$ ，考察以下问题：

你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的恰好一个货物移动至另一个。对 $i, i + 1$ （ $1 \le i < n$ ）号盒子做一次操作的代价为 $w_i$ 。注意：将 $i$ 号盒子的一个货物移动到 $i + 1$ 号盒子和将 $i + 1$ 号盒子的一个货物移动到 $i$ 号盒子的代价都是 $w_i$ 。你需要保证在操作中不存在盒子中的货物数量是负数。

在以上问题下，定义从初始状态达到第 $i$ 个盒子拥有恰好 $b_i$ 个货物的状态的最小代价为 $\operatorname{val}(b_1, b_2, \ldots, b_n)$ ，你需要求出对所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组 $(b_1, b_2, \ldots, b_n)$ ， $\operatorname{val}(b_1, b_2, \ldots, b_n)$ 的和。输出这个答案对 $998244353$ 取模后的结果。

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 $T$ ，表示测试数据组数。

对于每组数据，输入共三行。第一行一个正整数 $n$ 表示盒子的个数，第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 描述初始状态，第三行 $n - 1$ 个正整数 $w_1, w_2, \ldots, w_{n - 1}$ 描述移动货物的代价。

输出格式

对于每组测试数据输出一行一个整数，表示对于所有满足 $\sum_{i = 1}^{n} b_i = S$ 的非负整数数组，达到目标的代价的最小值之和模 $998244353$ 的结果。

样例 1

输入

输出

589248
8589

对于第一组数据，一共有六种需要考虑的情形，它们的 $b_1$ 和 $b_2$ 构成的二元组 $(b_1, b_2)$ 分别为 $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)$ 。

对于第一种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \times 2 = 130944$ 。
对于第二种情形，需要至少 $1$ 次移动，代价最小值为 $65472$ 。
对于第三种情形，不需要做任何操作，代价最小值为 $0$ 。
对于第四种情形，需要至少 $1$ 次移动，代价最小值为 $65472$ 。
对于第五种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \times 2 = 130944$ 。
对于最后一种情形，需要至少 $3$ 次移动，代价最小值为 $65472 \times 3 = 196416$ 。

因此，最小代价之和为 $130944 + 65472 + 0 + 65472 + 130944 + 196416 = 589248$。

样例 2-6

见附加文件中 box2.in 到 box6.in 和对应的 .ans 文件。

数据范围

保证对于任何测试点的任何一组数据，有 $2 \le n \le 5 \times 10^5$ ， $1 \le S \le 2 \times 10^6$ ， $a_i \ge 0$ ， $0 \le w_i < 998244353$ 。

测试点编号	$T \le$	$n \le$	$S \le$	特殊性质
1	1000	5		A
2
3		5	9	无
4
5	10	2000
6
7
8
9			$2 \times 10^5$
10
11
12
13	2	$2 \times 10^5$		B
14
15				AC
16
17				无
18
19	5	$5 \times 10^5$	$2 \times 10^6$
20

特殊性质说明：

A：对于任意 $1 \le i < n$ ， $w_i = 1$
B：对于任意 $1 \le i < n - 20$ ， $a_i = 0$
C：最多只有 $20$ 个 $i \in [1, n]$ 满足 $a_i \ne 0$

提示：本题有读入量较大的测试点，为了优化程序运行的时间，我们建议你采用较为快速的读入方式。

#L3739. 「LNOI2022」盒

「LNOI2022」盒