#P10003. cats 的凸包计算

    ID: 8225 传统题 8000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-凸包贡献法暴力枚举叉积乘法原理一维前缀和同向双指针对称性分析模逆元2024“钉耙编程”中国大学生算法设计超级联赛(8)

cats 的凸包计算

cats 的凸包计算

Problem Description

定义一个排列 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n 的面积为:将排列中的每个数 pip_i 看做二维坐标平面上的一个点 (i,pi)(i,p_i),这 nn 个点的凸包的面积。 现在 cats 有一个长为 nn 的数组 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,其中每个数均为一个 11 到 nn 之间的正整数或 −1-1。你需要求出将所有 −1-1 替换成 11 到 nn 之间的正整数后,形成的所有排列的面积之和对 109+710^9+7 取模的结果。 可以证明答案一定可以被表示为一个有理数 xy\frac{x}{y}。其中 xx 与 yy 互质。你需要输出 x⋅y−1 mod (109+7)x \cdot y^{-1} \bmod (10^9+7)。可以证明 (109+7)∤y(10^9+7) \nmid y。 注1:一个长为 nn 的数组 p1,p2,⋯pnp_1,p_2,\cdots p_n 是一个排列,当且仅当 11 到 nn 之间的每一个正整数都在 p1,p2,⋯pnp_1,p_2,\cdots p_n 中出现且仅出现一次。 注2:nn 个点 (x1,y1),(x2,y2),⋯ ,(xn,yn)(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n) 的凸包为:所有满足存在 nn 个范围在 [0,1][0,1] 之间的实数 w1,w2,⋯ ,wnw_1,w_2,\cdots,w_n ,使得 ∑i=1nwi=1\sum_{i=1}^n w_i =1,∑i=1nwi⋅xi=x\sum_{i=1}^n w_i\cdot x_i =x,∑i=1nwi⋅yi=y\sum_{i=1}^n w_i\cdot y_i =y 的点 (x,y)(x,y) 在二维坐标平面上组成的图形。

Input

第一行包含一个整数 TT (1≤T≤1000)(1\leq T \leq 1000),表示一共有 TT 组测试数据。 每组测试数据的第一行包含一个整数 nn (1≤n≤50)(1\leq n\leq 50),表示数组 aa 的长度。 每组测试数据的第二行包含 nn 个整数 a1,a2,⋯ana_1,a_2,\cdots a_n (−1≤ai≤n,ai≠0)(-1\leq a_i\leq n,a_i\neq 0),表示数组 aa。 保证对于任意的 1≤i<j≤n1\leq i< j\leq n,若 aia_i 和 aja_j 均不为 −1-1,则 ai≠aja_i \neq a_j。 保证所有测试数据的 n3n^3 之和不超过 5⋅1055\cdot 10^5。

Output

对于每组测试数据,输出一个整数,表示形成的所有排列的面积之和对 109+710^9+7 取模的结果。

Sample Input

5
3
1 2 3
4
2 -1 -1 3
4
1 2 -1 3
1
1
7
-1 -1 -1 -1 -1 -1 -1

Sample Output

0
9
500000006
0
99546

Source

2024“钉耙编程”中国大学生算法设计超级联赛(8)