{"problem":{"name":"[LNOI2022] 题","description":{"content":"给定长度为 $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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8366"},"statements":[{"statement_type":"Markdown","content":"给定长度为 $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}$，使得\n\n- $\\forall 1 \\le i \\le n$，$1 \\le a_{i, 1} < a_{i, 2} < a_{i, 3} \\le 3 n$；\n- $\\forall (i_1, j_1) \\ne (i_2, j_2)$，$a_{i_1, j_1} \\ne a_{i_2, j_2}$；\n- $\\forall 1 \\le i \\le n$，$\\{ t_{a_{i, 1}}, t_{a_{i, 2}}, t_{a_{i, 3}} \\}$ 是 $\\{ 1, 2, 3 \\}$ 的一个排列且逆序对数为奇数。\n\n认为两个方案本质不同当且仅当序列 $T$ 不同或存在 $a_{i, j}$（$1 \\le i \\le n$，$1 \\le j \\le 3$）不同，求以上操作的本质不同的方案数，对 $({10}^9 + 7)$ 取模。\n\n## Input\n\n**本题有多组测试数据**。输入的第一行包含一个正整数 $C$ 表示测试数据组数。\n\n对于每组测试数据，第一行一个整数 $n$，接下来一行一个长度为 $3 n$ 的字符串描述序列 $S$。\n\n## Output\n\n对于每组测试数据输出一行一个整数表示方案数对 $({10}^9 + 7)$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n前三组测试数据中 $n = 1$，故 $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 1, 2, 3 \\}$。\n\n对于第一组测试数据，只能有 $T = 123$，而 $\\{ 1, 2, 3 \\}$ 的逆序对数为 $0$ 不合法，故不存在方案。\n\n对于第二组测试数据，$T = 123$ 不合法，而 $T = 132$ 时 $\\{ 1, 3, 2 \\}$ 的逆序对数为 $1$ 合法，故存在一个方案。\n\n对于第三组测试数据，取 $T = 132$，$T = 213$，$T = 321$ 可以得到三个合法方案。\n\n对于第四组测试数据，$T = 321321$，有如下六种方案：\n\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 1, 2, 3 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 4, 5, 6 \\}$\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 4, 5, 6 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 1, 2, 3 \\}$\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 1, 2, 6 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 3, 4, 5 \\}$\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 3, 4, 5 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 1, 2, 6 \\}$\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 1, 5, 6 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 2, 3, 4 \\}$\n- $\\{ a_{1, 1}, a_{1, 2}, a_{1, 3} \\} = \\{ 2, 3, 4 \\}$，$\\{ a_{2, 1}, a_{2, 2}, a_{2, 3} \\} = \\{ 1, 5, 6 \\}$\n\n**【样例 \\#2】**\n\n见附件中的 ` problem/problem2.in` 与 `problem/problem2.ans`。\n\n该组样例中五组数据的 $n$ 分别为 $3, 5, 8, 12, 17$。\n\n**【样例 \\#3】**\n\n见选手目录下的 `problem/problem3.in` 与 `problem/problem3.ans`。\n\n该组样例满足特殊性质 A，五组数据的 $n$ 分别为 $2, 4, 7, 15, 19$。\n\n**【数据范围】**\n\n对于所有测试数据，$1 \\le C \\le 5$，$1 \\le n \\le 19$，字符串 $S$ 的长度为 $3 n$ 且仅由 $0, 1, 2, 3$ 构成。\n\n| 测试点编号 | $n \\le$ | 特殊性质 |\n|:-:|:-:|:-:|\n| $1$ | $1$ | 无 |\n| $2$ | $2$ | 无 |\n| $3$ | $3$ | 无 |\n| $4$ | $5$ | A |\n| $5$ | $7$ | 无 |\n| $6$ | $10$ | 无 |\n| $7$ | $13$ | A |\n| $8$ | $16$ | 无 |\n| $9$ | $18$ | 无 |\n| $10$ | $19$ | 无 |\n\n特殊性质 A：字符串 $S$ 由全 $0$ 的字符串构成。\n\n**【提示】**\n\n请注意程序的空间消耗。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8366","tags":["动态规划 DP","各省省选","2022","O2优化","辽宁"],"sample_group":[["5\n1\n123\n1\n100\n1\n000\n2\n321321\n2\n000001\n","0\n1\n3\n6\n60\n"]],"created_at":"2026-03-03 11:09:25"}}