{"problem":{"name":"[LNOI2022] 盒","description":{"content":"有 $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$ 个货物，为此你可以做如下操作若干次：对两个相","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8367"},"statements":[{"statement_type":"Markdown","content":"有 $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$，考察以下问题：\n\n你想让第 $i$ 个盒子中拥有恰好 $b_i$ 个货物，为此你可以做如下操作若干次：对两个相邻的盒子，把其中一个盒子的**恰好一个**货物移动至另一个。对 $i, i + 1$（$1 \\le i < n$）号盒子做**一次**操作的代价为 $w_i$。**注意：将 $\\bm{i}$ 号盒子的一个货物移动到 $\\bm{i + 1}$ 号盒子和将 $\\bm{i + 1}$ 号盒子的一个货物移动到 $\\bm{i}$ 号盒子的代价都是 $\\bm{w_i}$**。你需要保证在操作中不存在盒子中的货物数量是负数。\n\n在以上问题下，定义从初始状态达到第 $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$ 取模后的结果。\n\n## Input\n\n**本题有多组测试数据**。输入的第一行包含一个正整数 $T$，表示测试数据组数。\n\n对于每组数据，输入共三行。第一行一个正整数 $n$ 表示盒子的个数，第二行 $n$ 个非负整数 $a_1, a_2, \\ldots, a_n$ 描述初始状态，第三行 $n - 1$ 个非负整数 $w_1, w_2, \\ldots, w_{n - 1}$ 描述移动货物的代价。\n\n## Output\n\n对于每组测试数据输出一行一个整数，表示对于所有满足 $\\sum_{i = 1}^{n} b_i = S$ 的非负整数数组，达到目标的代价的最小值之和模 $998244353$ 的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n对于第一组数据，一共有六种需要考虑的情形，它们的 $b_1$ 和 $b_2$ 构成的二元组 $(b_1, b_2)$ 分别为 $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)$。\n\n对于第一种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \\times 2 = 130944$。\n\n对于第二种情形，需要至少 $1$ 次移动，代价最小值为 $65472$。\n\n对于第三种情形，不需要做任何操作，代价最小值为 $0$。\n\n对于第四种情形，需要至少 $1$ 次移动，代价最小值为 $65472$。\n\n对于第五种情形，需要至少 $2$ 次移动，代价最小值为 $65472 \\times 2 = 130944$。\n\n对于最后一种情形，需要至少 $3$ 次移动，代价最小值为 $65472 \\times 3 = 196416$。\n\n因此，最小代价之和为 $130944 + 65472 + 0 + 65472 + 130944 + 196416 = 589248$。\n\n**【样例 \\#2】**\n\n见附件中的 `box/box2.in` 与 `box/box2.ans`。\n\n这个样例满足测试点 $5 \\sim 8$ 的限制。\n\n**【样例 \\#3】**\n\n见附件中的 `box/box3.in` 与 `box/box3.ans`。\n\n这个样例满足测试点 $9 \\sim 12$ 的限制。\n\n**【样例 \\#4】**\n\n见附件中的 `box/box4.in` 与 `box/box4.ans`。\n\n这个样例满足测试点 $13 \\sim 14$ 的限制。\n\n**【样例 \\#5】**\n\n见附件中的 `box/box5.in` 与 `box/box5.ans`。\n\n这个样例满足测试点 $15 \\sim 16$ 的限制。\n\n**【样例 \\#6】**\n\n见附件中的 `box/box6.in` 与 `box/box6.ans`。\n\n这个样例满足测试点 $17 \\sim 18$ 的限制。\n\n**【数据范围】**\n\n保证对于任何测试点的任何一组数据，有 $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$。\n\n| 测试点编号 | $T \\le$ | $n \\le$ | $S \\le$ | 特殊性质 |\n|:-:|:-:|:-:|:-:|:-:|\n| $1 \\sim 2$ | $1000$ | $5$ | $5$ | A |\n| $3 \\sim 4$ | $5$ | $9$ | $9$ | 无 |\n| $5 \\sim 8$ | $10$ | $2000$ | $2000$ | 无 |\n| $9 \\sim 12$ | $10$ | $2000$ | $2 \\times {10}^5$ | 无 |\n| $13 \\sim 14$ | $2$ | $2 \\times {10}^5$ | $2 \\times {10}^5$ | B |\n| $15 \\sim 16$ | $2$ | $2 \\times {10}^5$ | $2 \\times {10}^5$ | AC |\n| $17 \\sim 18$ | $2$ | $2 \\times {10}^5$ | $2 \\times {10}^5$ | 无 |\n| $19 \\sim 20$ | $5$ | $5 \\times {10}^5$ | $2 \\times {10}^6$ | 无 |\n\n特殊性质 A：对于任意 $1 \\le i < n$，$w_i = 1$。  \n特殊性质 B：对于任意 $1 \\le i < n - 20$，$a_i = 0$。  \n特殊性质 C：最多只有 $20$ 个 $i \\in [1, n]$ 满足 $a_i \\ne 0$。\n\n**【提示】**\n\n本题有读入量较大的测试点，为了优化程序运行的时间，我们建议你采用较为快速的读入方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8367","tags":["各省省选","2022","O2优化","辽宁"],"sample_group":[["2\n2\n2 3\n65472\n5\n1 3 2 1 1\n2 3 3 3\n","589248\n8589\n"]],"created_at":"2026-03-03 11:09:25"}}