{"problem":{"name":"「KDOI-03」构造数组","description":{"content":"你现在有一个长度为 $n$ 的数组 $a$。一开始，所有 $a_i$ 均为 $0$。给出一个同样长度为 $n$ 的目标数组 $b$。求有多少种方案，使得通过若干次以下操作，可以让 $a$ 数组变成 $b$。 * 选出两个**不同的**下标 $1\\leq i<j\\leq n$，并将 $a_i$ 和 $a_j$ 同时增加 $1$。 两种方案被称之为不同的，当且仅当存在一个 $x$ 使得一种方案中第","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8863"},"statements":[{"statement_type":"Markdown","content":"你现在有一个长度为 $n$ 的数组 $a$。一开始，所有 $a_i$ 均为 $0$。给出一个同样长度为 $n$ 的目标数组 $b$。求有多少种方案，使得通过若干次以下操作，可以让 $a$ 数组变成 $b$。\n\n* 选出两个**不同的**下标 $1\\leq i<j\\leq n$，并将 $a_i$ 和 $a_j$ 同时增加 $1$。\n\n两种方案被称之为不同的，当且仅当存在一个 $x$ 使得一种方案中第 $x$ 次操作选择的两个下标 $(i,j)$ 与另一种方案中的不同。\n\n**答案对 $\\bm{998244353}$ 取模。**\n\n## Input\n\n从标准输入读入数据。\n\n输入数据一共包含两行。\n\n第一行包含一个正整数 $n$。\n\n第二行包含 $n$ 个正整数，表示 $b_1,b_2,\\ldots,b_n$。\n\n## Output\n\n输出到标准输出。\n\n输出一行一个正整数，表示将 $a$ 数组通过若干次操作变成 $b$ 数组的方案数对 $998244353$ 取模后的结果。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n| 种类编号 | 第一组 | 第二组 | 第三组 | 第四组 | 方案数 |\n| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | `1<->2` | `1<->2` | `3<->4` | `3<->4` | $\\binom{4}{2}=6$ |\n| $2$ | `1<->3` | `1<->3` | `2<->4` | `2<->4` | $\\binom{4}{2}=6$ |\n| $3$ | `1<->4` | `1<->4` | `2<->3` | `2<->3` | $\\binom{4}{2}=6$ |\n| $4$ | `1<->2` | `1<->4` | `2<->3` | `3<->4` | $4!=24$ |\n| $5$ | `1<->2` | `1<->3` | `2<->4` | `3<->4` | $4!=24$ |\n| $6$ | `1<->3` | `1<->4` | `2<->3` | `2<->4` | $4!=24$ |\n\n总方案数是 $6\\times3+24\\times3=90$。\n\n**【样例 2】**\n\n见选手文件中的 `array/array2.in` 与 `array/array2.ans`。\n\n此样例满足测试点 $6\\sim8$ 的限制。\n\n**【样例 3】**\n\n见选手文件中的 `array/array3.in` 与 `array/array3.ans`。\n\n此样例满足测试点 $12\\sim14$ 的限制。\n\n**【样例 4】**\n\n见选手文件中的 `array/array4.in` 与 `array/array4.ans`。\n\n此样例满足测试点 $15\\sim18$ 的限制。\n\n**【样例 5】**\n\n见选手文件中的 `array/array5.in` 与 `array/array5.ans`。\n\n此样例满足测试点 $19\\sim20$ 的限制。\n\n**【样例 6】**\n\n见选手文件中的 `array/array6.in` 与 `array/array6.ans`。\n\n此样例满足测试点 $21\\sim22$ 的限制。\n\n**【样例 7】**\n\n见选手文件中的 `array/array7.in` 与 `array/array7.ans`。\n\n此样例满足测试点 $23\\sim25$ 的限制。\n\n***\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1\\le n\\le5~000$，$1\\leq b_i\\le3 \\times 10^4$，$\\sum b_i\\le3 \\times 10^4$。\n\n| 测试点编号 | $n$ | $\\sum b_i$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $\\leq5~000$ | $\\equiv 1\\pmod 2$ |\n| $2\\sim3$ | $=1$ | $\\leq3 \\times 10^4$ |\n| $4\\sim5$ | $=2$ | $\\leq3 \\times 10^4$ |\n| $6\\sim8$ | $\\leq5$ | $\\leq8$ |\n| $9\\sim11$ | $\\leq20$ | $=n$ |\n| $12\\sim14$ | $\\leq 5~000$ | $=n$ |\n| $15\\sim18$ | $\\leq16$ | $\\leq16$ |\n| $19\\sim20$ | $\\le 700$ | $\\le700$ |\n| $21\\sim22$ | $\\le 5~000$ | $\\le5~000$ |\n| $23\\sim25$ | $\\le5~000$ | $\\le3 \\times 10^4$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8863","tags":["动态规划 DP","2022","洛谷原创","O2优化","动态规划优化","组合数学"],"sample_group":[["4\n2 2 2 2","90"]],"created_at":"2026-03-03 11:09:25"}}