QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 4223. 盒

统计

有 $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$。注意:将 $\boldsymbol{i}$ 号盒子的一个货物移动到 $\boldsymbol{i + 1}$ 号盒子和将 $\boldsymbol{i + 1}$ 号盒子的一个货物移动到 $\boldsymbol{i}$ 号盒子的代价都是 $\boldsymbol{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 输入

2
2
2 3
65472
5
1 3 2 1 1
2 3 3 3

样例 1 输出

589248
8589

样例 1 解释

对于第一组数据,一共有六种需要考虑的情形,它们的 $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

见下发文件。

这个样例满足测试点 $5 \sim 8$ 的限制。

样例 3

见下发文件。

这个样例满足测试点 $9 \sim 12$ 的限制。

样例 4

见下发文件。

这个样例满足测试点 $13 \sim 14$ 的限制。

样例 5

见下发文件。

这个样例满足测试点 $15 \sim 16$ 的限制。

样例 6

见下发文件。

这个样例满足测试点 $15 \sim 16$ 的限制。

子任务

保证对于任何测试点的任何一组数据,有 $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$ $5$ A
$2$ $1000$ $5$ $5$ A
$3$ $5$ $9$ $9$
$4$ $5$ $9$ $9$
$5$ $10$ $2000$ $2000$
$6$ $10$ $2000$ $2000$
$7$ $10$ $2000$ $2000$
$8$ $10$ $2000$ $2000$
$9$ $10$ $2000$ $2 \times {10}^5$
$10$ $10$ $2000$ $2 \times {10}^5$
$11$ $10$ $2000$ $2 \times {10}^5$
$12$ $10$ $2000$ $2 \times {10}^5$
$13$ $2$ $2 \times {10}^5$ $2 \times {10}^5$ B
$14$ $2$ $2 \times {10}^5$ $2 \times {10}^5$ B
$15$ $2$ $2 \times {10}^5$ $2 \times {10}^5$ AC
$16$ $2$ $2 \times {10}^5$ $2 \times {10}^5$ AC
$17$ $2$ $2 \times {10}^5$ $2 \times {10}^5$
$18$ $2$ $2 \times {10}^5$ $2 \times {10}^5$
$19$ $5$ $5 \times {10}^5$ $2 \times {10}^6$
$20$ $5$ $5 \times {10}^5$ $2 \times {10}^6$
  • 特殊性质 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$。

提示

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