[LNOI2022] 题
题目描述
给定长度为 $3 n$、值域为 $[0, 3]$ 的整数序列 $S = s_1 s_2 \cdots s_{3 n}$。你需要首先将 $S$ 中的每个 $0$ 替换为 $[1, 3]$ 中的任意一个整数,得到序列 $T = t_1 t_2 \cdots t_{3 n}$,然后给出 $n$ 个长度为 $3$ 的整数序列 ${\{ a_{i, 1}, a_{i, 2}, a_{i, 3} \}}_{1 \le i \le n}$,使得
- $\forall 1 \le i \le n$,$1 \le a_{i, 1} < a_{i, 2} < a_{i, 3} \le 3 n$;
- $\forall (i_1, j_1) \ne (i_2, j_2)$,$a_{i_1, j_1} \ne a_{i_2, j_2}$;
- $\forall 1 \le i \le n$,$\{ t_{a_{i, 1}}, t_{a_{i, 2}}, t_{a_{i, 3}} \}$ 是 $\{ 1, 2, 3 \}$ 的一个排列且逆序对数为奇数。
认为两个方案本质不同当且仅当序列 $T$ 不同或存在 $a_{i, j}$($1 \le i \le n$,$1 \le j \le 3$)不同,求以上操作的本质不同的方案数,对 $({10}^9 + 7)$ 取模。
输入输出格式
输入格式
**本题有多组测试数据**。输入的第一行包含一个正整数 $C$ 表示测试数据组数。
对于每组测试数据,第一行一个整数 $n$,接下来一行一个长度为 $3 n$ 的字符串描述序列 $S$。
输出格式
对于每组测试数据输出一行一个整数表示方案数对 $({10}^9 + 7)$ 取模的结果。
输入输出样例
输入样例 #1
5
1
123
1
100
1
000
2
321321
2
000001
输出样例 #1
0
1
3
6
60
说明
**【样例解释 \#1】**
前三组测试数据中 $n = 1$,故 $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 3 \}$。
对于第一组测试数据,只能有 $T = 123$,而 $\{ 1, 2, 3 \}$ 的逆序对数为 $0$ 不合法,故不存在方案。
对于第二组测试数据,$T = 123$ 不合法,而 $T = 132$ 时 $\{ 1, 3, 2 \}$ 的逆序对数为 $1$ 合法,故存在一个方案。
对于第三组测试数据,取 $T = 132$,$T = 213$,$T = 321$ 可以得到三个合法方案。
对于第四组测试数据,$T = 321321$,有如下六种方案:
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 3 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 4, 5, 6 \}$
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 4, 5, 6 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 2, 3 \}$
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 2, 6 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 3, 4, 5 \}$
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 3, 4, 5 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 2, 6 \}$
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 1, 5, 6 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 2, 3, 4 \}$
- $\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \} = \{ 2, 3, 4 \}$,$\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \} = \{ 1, 5, 6 \}$
**【样例 \#2】**
见附件中的 ` problem/problem2.in` 与 `problem/problem2.ans`。
该组样例中五组数据的 $n$ 分别为 $3, 5, 8, 12, 17$。
**【样例 \#3】**
见选手目录下的 `problem/problem3.in` 与 `problem/problem3.ans`。
该组样例满足特殊性质 A,五组数据的 $n$ 分别为 $2, 4, 7, 15, 19$。
**【数据范围】**
对于所有测试数据,$1 \le C \le 5$,$1 \le n \le 19$,字符串 $S$ 的长度为 $3 n$ 且仅由 $0, 1, 2, 3$ 构成。
| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1$ | $1$ | 无 |
| $2$ | $2$ | 无 |
| $3$ | $3$ | 无 |
| $4$ | $5$ | A |
| $5$ | $7$ | 无 |
| $6$ | $10$ | 无 |
| $7$ | $13$ | A |
| $8$ | $16$ | 无 |
| $9$ | $18$ | 无 |
| $10$ | $19$ | 无 |
特殊性质 A:字符串 $S$ 由全 $0$ 的字符串构成。
**【提示】**
请注意程序的空间消耗。