[AGC030F] Permutation and Minimum
题意翻译
有一个 $2 N$ 个数的序列 $A$，从 $1$ 到 $2 N$ 标号。你要把 $1 \sim 2 N$ 这些数填进去，使它形成一个排列。
但是已经有一些位置强制填了特定的数了，输入时会给出。
最后令长度为 $N$ 的序列 $B$ 为：令 $B_i = \min\{A_{2 i - 1}, A_{2 i}\}$。
询问所有方案中能得到的不同的 $B$ 的数量。
- $1 \le N \le 300$。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc030/tasks/agc030_f
長さ $ 2N $ の数列 $ A_1,\ A_2,\ ...,\ A_{2N} $ があります． 各 $ A_i $ は $ -1 $ か，あるいは $ 1 $ 以上 $ 2N $ 以下の整数です． $ -1 $ 以外のどの整数も，$ {A_i} $ の中には $ 1 $ 回までしか現れません．
すぬけ君は，$ A_i\ =\ -1 $ であるような $ i $ それぞれに対して，$ A_i $ を $ 1 $ 以上 $ 2N $ の整数で置き換えて，$ {A_i} $ が $ 1,\ 2,\ ...,\ 2N $ の並び替えになるようにします． そして，長さ $ N $ の数列 $ B_1,\ B_2,\ ...,\ B_N $ を，$ B_i\ =\ min(A_{2i-1},\ A_{2i}) $ として求めます．
数列 $ B_1,\ B_2,\ ...,\ B_N $ として考えられる異なるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを求めてください．
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる．
> $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_{2N} $
输出格式
数列 $ B_1,\ B_2,\ ...,\ B_N $ として考えられる異なるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを出力せよ．
输入输出样例
输入样例 #1
3
1 -1 -1 3 6 -1输出样例 #1
5输入样例 #2
4
7 1 8 3 5 2 6 4输出样例 #2
1输入样例 #3
10
7 -1 -1 -1 -1 -1 -1 6 14 12 13 -1 15 -1 -1 -1 -1 20 -1 -1输出样例 #3
9540576输入样例 #4
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输出样例 #4
374984201说明
### 制約
- $ 1\ \leq\ N\ \leq\ 300 $
- $ A_i\ =\ -1 $ あるいは $ 1\ \leq\ A_i\ \leq\ 2N $
- $ A_i\ \neq\ -1,\ A_j\ \neq\ -1 $ ならば $ A_i\ \neq\ A_j $ ($ i\ \neq\ j $)
### Sample Explanation 1
$ {A_i} $ を $ 1,\ 2,\ ...,\ 2N $ の並び替えにする方法は $ 6 $ 通りありますが，そのそれぞれに対して $ {B_i} $ は次のようになります： - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 2,\ 4,\ 3,\ 6,\ 5) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 3,\ 5) $ - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 2,\ 5,\ 3,\ 6,\ 4) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 3,\ 4) $ - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 4,\ 2,\ 3,\ 6,\ 5) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 2,\ 5) $ - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 4,\ 5,\ 3,\ 6,\ 2) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 3,\ 2) $ - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 5,\ 2,\ 3,\ 6,\ 4) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 2,\ 4) $ - $ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (1,\ 5,\ 4,\ 3,\ 6,\ 2) $: $ (B_1,\ B_2,\ B_3)\ =\ (1,\ 3,\ 2) $ よって，異なる $ B_1,\ B_2,\ B_3 $ は $ 5 $ 個あります．