P8863 「KDOI-03」构造数组

你现在有一个长度为 $n$ 的数组 $a$。一开始，所有 $a_i$ 均为 $0$。给出一个同样长度为 $n$ 的目标数组 $b$。求有多少种方案，使得通过若干次以下操作，可以让 $a$ 数组变成 $b$。 * 选出两个**不同的**下标 $1\leq i

无

无

**【样例 1 解释】** | 种类编号 | 第一组 | 第二组 | 第三组 | 第四组 | 方案数 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | `12` | `12` | `34` | `34` | $\binom{4}{2}=6$ | | $2$ | `13` | `13` | `24` | `24` | $\binom{4}{2}=6$ | | $3$ | `14` | `14` | `23` | `23` | $\binom{4}{2}=6$ | | $4$ | `12` | `14` | `23` | `34` | $4!=24$ | | $5$ | `12` | `13` | `24` | `34` | $4!=24$ | | $6$ | `13` | `14` | `23` | `24` | $4!=24$ | 总方案数是 $6\times3+24\times3=90$。 **【样例 2】** 见选手文件中的 `array/array2.in` 与 `array/array2.ans`。 此样例满足测试点 $6\sim8$ 的限制。 **【样例 3】** 见选手文件中的 `array/array3.in` 与 `array/array3.ans`。 此样例满足测试点 $12\sim14$ 的限制。 **【样例 4】** 见选手文件中的 `array/array4.in` 与 `array/array4.ans`。 此样例满足测试点 $15\sim18$ 的限制。 **【样例 5】** 见选手文件中的 `array/array5.in` 与 `array/array5.ans`。 此样例满足测试点 $19\sim20$ 的限制。 **【样例 6】** 见选手文件中的 `array/array6.in` 与 `array/array6.ans`。 此样例满足测试点 $21\sim22$ 的限制。 **【样例 7】** 见选手文件中的 `array/array7.in` 与 `array/array7.ans`。 此样例满足测试点 $23\sim25$ 的限制。 *** **【数据范围】** 对于 $100\%$ 的数据，$1\le n\le5~000$，$1\leq b_i\le30~000$，$\sum b_i\le30~000$。 | 测试点编号 | $n$ | $\sum b_i$ | | :----------: | :----------: | :----------: | | $1$ | $\leq5~000$ | $\equiv 1\pmod 2$ | | $2\sim3$ | $=1$ | $\leq30~000$ | | $4\sim5$ | $=2$ | $\leq30~000$ | | $6\sim8$ | $\leq5$ | $\leq8$ | | $9\sim11$ | $\leq20$ | $=n$ | | $12\sim14$ | $\leq 5~000$ | $=n$ | | $15\sim18$ | $\leq16$ | $\leq16$ | | $19\sim20$ | $\le 700$ | $\le700$ | | $21\sim22$ | $\le 5~000$ | $\le5~000$ | | $23\sim25$ | $\le5~000$ | $\le30~000$ |