题目描述
長さ 2N の数列 A1, A2, ..., A2N があります. 各 Ai は −1 か,あるいは 1 以上 2N 以下の整数です. −1 以外のどの整数も,Ai の中には 1 回までしか現れません.
すぬけ君は,Ai = −1 であるような i それぞれに対して,Ai を 1 以上 2N の整数で置き換えて,Ai が 1, 2, ..., 2N の並び替えになるようにします. そして,長さ N の数列 B1, B2, ..., BN を,Bi = min(A2i−1, A2i) として求めます.
数列 B1, B2, ..., BN として考えられる異なるものの個数を 109 + 7 で割ったあまりを求めてください.
输入格式
入力は以下の形式で標準入力から与えられる.
N A1 A2 ... A2N
输出格式
数列 B1, B2, ..., BN として考えられる異なるものの個数を 109 + 7 で割ったあまりを出力せよ.
题目大意
有一个 2N 个数的序列 A,从 1 到 2N 标号。你要把 1∼2N 这些数填进去,使它形成一个排列。
但是已经有一些位置强制填了特定的数了,输入时会给出。
最后令长度为 N 的序列 B 为:令 Bi=min{A2i−1,A2i}。
询问所有方案中能得到的不同的 B 的数量。
- 1≤N≤300。
3
1 -1 -1 3 6 -1
5
4
7 1 8 3 5 2 6 4
1
10
7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1
9540576
20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 34 -1 -1 -1 -1 31 -1 -1 -1 -1 -1 -1 -1 -1
374984201
提示
制約
- 1 ≤ N ≤ 300
- Ai = −1 あるいは 1 ≤ Ai ≤ 2N
- Ai = −1, Aj = −1 ならば Ai = Aj (i = j)
Sample Explanation 1
Ai を 1, 2, ..., 2N の並び替えにする方法は 6 通りありますが,そのそれぞれに対して Bi は次のようになります: - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 2,\ 4,\ 3,\ 6,\ 5) $: (B1, B2, B3) = (1, 3, 5) - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 2,\ 5,\ 3,\ 6,\ 4) $: (B1, B2, B3) = (1, 3, 4) - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 4,\ 2,\ 3,\ 6,\ 5) $: (B1, B2, B3) = (1, 2, 5) - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 4,\ 5,\ 3,\ 6,\ 2) $: (B1, B2, B3) = (1, 3, 2) - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 5,\ 2,\ 3,\ 6,\ 4) $: (B1, B2, B3) = (1, 2, 4) - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 5,\ 4,\ 3,\ 6,\ 2) $: (B1, B2, B3) = (1, 3, 2) よって,異なる B1, B2, B3 は 5 個あります.