← 返回题目列表

Codeforces · 2084/E

E. 开花

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$$$^{\text{∗}}$$$ 的排列 $$$a$$$,其中缺少一些元素并用 $$$-1$$$ 表示。

将排列的值定义为其所有非空子段$$$^{\text{‡}}$$$ 的 MEX$$$^{\text{†}}$$$ 之和。

求所有可能的有效排列的值之和,这些排列可以通过填充 $$$a$$$ 的缺失元素以 $$$10^9 + 7$$$ 为模来形成。

$$$^{\text{*}}$$$ 长度 $$$n$$$ 的排列是由 $$$n$$$ 不同整数组成的数组 从 $$$\bf{0}$$$ 到 $$$\bf{n - 1}$$$ 以任意顺序。例如,$$$[1,2,0,4,3]$$$是一个排列,但$$$[0,1,1]$$$不是排列($$$1$$$在数组中出现两次),$$$[0,2,3]$$$也不是排列($$$n=3$$$但数组中有$$$3$$$)。

$$$^{\text{†}}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

$$$^{\text{‡}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子段,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \lt n$$$)。

保证 $$$a$$$ 中不是 $$$-1$$$ 的元素是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个整数 - 所有可能的有效排列模 $$$10^9 + 7$$$ 的值之和。

示例

输入
复制

5
2
0 -1
2
-1 -1
3
2 0 1
3
-1 2 -1
5
-1 0 -1 2 -1

输出
复制

3
6
7
10
104

注意

在第一个测试用例中,唯一有效的排列是 $$$[0, 1]$$$,$$$[0, 1]$$$ 的值为 $$$3$$$,因为:

$$$$$$\operatorname{mex}([0]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 1]) = 1 + 0 + 2 = 3$$$$$$

所以答案是$$$3$$$。

在第二个测试用例中,有两个有效排列:$$$[0, 1]$$$ 和 $$$[1, 0]$$$。 $$$[0, 1]$$$ 的值和 $$$[1, 0]$$$ 的值是 $$$3$$$,所以答案是 $$$3 + 3 = 6$$$。

在第四个测试用例中,有两个有效排列:$$$[0, 2, 1]$$$ 和 $$$[1, 2, 0]$$$。 $$$[0, 2, 1]$$$ 的值为 $$$5$$$,因为:

$$$$$$\operatorname{mex}([0]) + \operatorname{mex}([2]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 2]) + \operatorname{mex}([2, 1]) + \operatorname{mex}([0, 2, 1]) = 1 + 0 + 0 + 1 + 0 + 3 = 5$$$$$$

$$$[1, 2, 0]$$$ 的值为 $$$5$$$,因为:

$$$$$$\operatorname{mex}([1]) + \operatorname{mex}([2]) + \operatorname{mex}([0]) + \operatorname{mex}([1, 2]) + \operatorname{mex}([2, 0]) + \operatorname{mex}([1, 2, 0]) = 0 + 0 + 1 + 0 + 1 + 3 = 5$$$$$$

所以答案是 $$$5 + 5 = 10$$$。