P8367 [LNOI2022] Box

There are $n$ distinct boxes in a row. Initially, the $i$-th box contains $a_i$ items, and the total number of items is $S = \sum_{i = 1}^{n} a_i$. For a non-negative integer array $(b_1, b_2, \ldots, b_n)$ satisfying $\sum_{i = 1}^{n} b_i = S$, consider the following problem: You want the $i$-th box to contain exactly $b_i$ items. To achieve this, you may perform the following operation any number of times: for two adjacent boxes, move **exactly one** item from one box to the other. The cost of performing **one** operation on boxes $i$ and $i + 1$ ($1 \le i < n$) is $w_i$. **Note: moving one item from box $\bm{i}$ to box $\bm{i + 1}$ and moving one item from box $\bm{i + 1}$ to box $\bm{i}$ both cost $\bm{w_i}$**. You must ensure that during the operations, no box ever has a negative number of items. Under the above setting, define the minimum cost to reach a state where the $i$-th box contains exactly $b_i$ items from the initial state as $\operatorname{val}(b_1, b_2, \ldots, b_n)$. You need to compute, over all non-negative integer arrays $(b_1, b_2, \ldots, b_n)$ satisfying $\sum_{i = 1}^{n} b_i = S$, the sum of $\operatorname{val}(b_1, b_2, \ldots, b_n)$. Output the answer modulo $998244353$.

**This problem has multiple test cases**. The first line contains a positive integer $T$, the number of test cases. For each test case, the input consists of three lines. The first line contains a positive integer $n$, the number of boxes. The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ describing the initial state. The third line contains $n - 1$ non-negative integers $w_1, w_2, \ldots, w_{n - 1}$ describing the cost of moving items.

For each test case, output one integer per line: the sum, over all non-negative integer arrays satisfying $\sum_{i = 1}^{n} b_i = S$, of the minimum cost to reach the target state, modulo $998244353$.

**[Sample Explanation \#1]** For the first test case, there are six cases to consider. The pairs $(b_1, b_2)$ are $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)$. In the first case, at least $2$ moves are needed, and the minimum cost is $65472 \times 2 = 130944$. In the second case, at least $1$ move is needed, and the minimum cost is $65472$. In the third case, no operation is needed, and the minimum cost is $0$. In the fourth case, at least $1$ move is needed, and the minimum cost is $65472$. In the fifth case, at least $2$ moves are needed, and the minimum cost is $65472 \times 2 = 130944$. In the last case, at least $3$ moves are needed, and the minimum cost is $65472 \times 3 = 196416$. Therefore, the sum of minimum costs is $130944 + 65472 + 0 + 65472 + 130944 + 196416 = 589248$. **[Sample \#2]** See `box/box2.in` and `box/box2.ans` in the attachment. This sample satisfies the constraints of test points $5 \sim 8$. **[Sample \#3]** See `box/box3.in` and `box/box3.ans` in the attachment. This sample satisfies the constraints of test points $9 \sim 12$. **[Sample \#4]** See `box/box4.in` and `box/box4.ans` in the attachment. This sample satisfies the constraints of test points $13 \sim 14$. **[Sample \#5]** See `box/box5.in` and `box/box5.ans` in the attachment. This sample satisfies the constraints of test points $15 \sim 16$. **[Sample \#6]** See `box/box6.in` and `box/box6.ans` in the attachment. This sample satisfies the constraints of test points $17 \sim 18$. **[Constraints]** It is guaranteed that for every test point and every test case: $2 \le n \le 5 \times {10}^5$, $1 \le S \le 2 \times {10}^6$, $a_i \ge 0$, and $0 \le w_i < 998244353$. | Test Point ID | $T \le$ | $n \le$ | $S \le$ | Special Properties | |:-:|:-:|:-:|:-:|:-:| | $1 \sim 2$ | $1000$ | $5$ | $5$ | A | | $3 \sim 4$ | $5$ | $9$ | $9$ | None | | $5 \sim 8$ | $10$ | $2000$ | $2000$ | None | | $9 \sim 12$ | $10$ | $2000$ | $2 \times {10}^5$ | None | | $13 \sim 14$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | B | | $15 \sim 16$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | AC | | $17 \sim 18$ | $2$ | $2 \times {10}^5$ | $2 \times {10}^5$ | None | | $19 \sim 20$ | $5$ | $5 \times {10}^5$ | $2 \times {10}^6$ | None | Special Property A: For any $1 \le i < n$, $w_i = 1$. Special Property B: For any $1 \le i < n - 20$, $a_i = 0$. Special Property C: There are at most $20$ indices $i \in [1, n]$ such that $a_i \ne 0$. **[Hint]** Some test points have a large input size. To optimize runtime, it is recommended to use a faster input method. Translated by ChatGPT 5