原题呈现

P8366 [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#

输入 #1#

输出 #1#

说明/提示#

【样例解释 #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 \}$

【数据范围】

对于所有测试数据， $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$ 的字符串构成．

【提示】

请注意程序的空间消耗．

思路#

观察到数据范围中 $n$ 很小，所以可以选择使用高次的 DP．

不难发现，一个序列是 $\{ 1, 2, 3 \}$ 的一个排列且逆序对数为奇数，当且仅当这个序列属于 $\{\{1,3,2\}, \{2, 1, 3\}, \{3, 2, 1\}\}$ ．

遍历整个序列，若当前元素为 1（或 0），则可以是：

单独的一个 $\{1\}$
和前面的 $\{2\}$ 组合成 $\{2, 1\}$
和前面的 $\{3,2\}$ 组合成 $\{3, 2, 1\}$

若当前元素为 2 或 3 时同理．

依照这个设计状态：dp[i][a][b][c][d][e][f]，用于表示考虑到第 $i$ 个元素时：

前面剩余单独的 $\{1\}$ 有 a 个
前面剩余单独的 $\{2\}$ 有 b 个
前面剩余单独的 $\{3\}$ 有 c 个
前面剩余的 $\{2, 1\}$ 有 d 个
前面剩余的 $\{1, 3\}$ 有 e 个
前面剩余的 $\{3, 2\}$ 有 f 个的方案数量．

初始时，dp[0][0][0][0][0][0][0] = 1 表示前 0 个元素时，肯定什么都没有剩余，此时仅一种方案．

接着，遍历整个序列，若当前元素为 2（或 0），则 dp[i][a][b][c][d][e][f] 可以增加：

dp[i-1][a][b-1][c][d][e][f]，增加了一个单独的 $\{1\}$
dp[i-1][a][b][c+1][d][e][f-1] * (c+1)，花费任意一个 $\{3\}$ （由于有 $c+1$ 个 $\{3\}$ ，所以有 $c+1$ 种选法），增加了一个 $\{3, 2\}$
dp[i-1][a][b][c][d][e+1][f] * (e+1)，花费一个 $\{1，3\}$ （同理，有 $e+1$ 种选法），组成了一个 $\{1,3,2\}$ ，这个组合合法，消去．

若当前元素为 1 或 3 时同理．

最终状态为 dp[3*n][0][0][0][0][0][0]．

观察得出 dp[i][...] 只与 dp[i-1][...] 有关，因此使用滚动数组优化．

什么是滚动数组？

滚动数组，是一种节省空间的做法，一般来说，如果 dp[i][...] 只与 dp[i-x][...]（x 为常数，且 x 通常为 1）有关时，可以使用滚动数组．

以 x=1 为例，在计算完 dp[0][...] 和 dp[1][...] 之后，由于之后的计算不再需要用到 dp[0][...]，因此，可以将 dp[2][...] 存放在 dp[0][...] 的位置，从而达到节省空间的目的．

在实现时，常常定义 cur = i & 1 和 pre = (i-1) & 1，利用 dp[cur][...] 来代替 dp[i][...]，dp[pre][...] 来代替 dp[i-1][...]．

由于算出来的是划分数，而题目要求的是排列，所以还要乘 $n!$ ．

1
#include <bits/stdc++.h>
2
#define allow_one(x) ((x) <= i && (x) <= n)
3
typedef long long ll;
4
using namespace std;
5
const int N = 60;
6
const int MOD = 1e9 + 7;
7
int n, A[N];
8
ll fac[N];
9
ll calFac(int x) {
10
    if (fac[x] == 0) {
11
        fac[x] = (1ll * calFac(x - 1) * x) % MOD;
12
    }
13
    return fac[x];
14
}
15
// dp[one][two][three][oneTwo][oneThree][twoThree]
16
// {1,3,2},{2,1,3},{3,2,1} 是合法的
17
int dp[2][21][21][21][21][21][21];
18
void solve() {
19
    memset(dp, 0, sizeof(dp));
20
    cin >> n;
21
    string str;
22
    cin >> str;
23
    for (int i = 0; i < str.size(); i++) {
24
        A[i + 1] = str[i] - '0';
25
    }
26
    dp[0][0][0][0][0][0][0] = 1;
27
    for (int i = 1; i <= 3 * n; i++) {
28
        int pre = (i - 1) & 1, now = i & 1;
29
        for (int a = 0; allow_one(a); a++)
30
            for (int b = 0; allow_one(a + b); b++)
31
                for (int c = 0; allow_one(a + b + c); c++)
32
                    for (int d = 0;
33
                         a + b + c + d <= n && a + b + c + 2 * d <= i; d++)
34
                        for (int e = 0;
35
                             e <= n && a + b + c + 2 * d + 2 * e <= i &&
36
                             a + b + c + d + e <= n;
37
                             e++)
38
                            for (int f = 0;
39
                                 f <= n &&
40
                                 a + b + c + 2 * d + 2 * e + 2 * f <= i &&
41
                                 a + b + c + d + e + f <= n;
42
                                 f++) {
43
                                ll cur = 0; // 清零
44
                                if (A[i] == 1 || A[i] == 0) {
45
                                    // 新增一个 1
46
                                    if (a - 1 >= 0)
47
                                        cur = (cur +
48
                                               dp[pre][a - 1][b][c][d][e][f]) %
49
                                              MOD;
50
                                    // 与已有的 2 结合成 {2,1}，消耗 b，增加 d
51
                                    if (d - 1 >= 0)
52
                                        cur = (cur + 1ll *
53
                                                         dp[pre][a][b + 1][c]
54
                                                           [d - 1][e][f] *
55
                                                         (b + 1)) %
56
                                              MOD;
57
                                    // 与已有的 {3,2} 完成，消耗 f
58
                                    if (f < n) // 保证 f+1 不越界
59
                                        cur =
60
                                            (cur +
61
                                             1ll *
62
                                                 dp[pre][a][b][c][d][e][f + 1] *
63
                                                 (f + 1)) %
64
                                            MOD;
65
                                }
66
                                if (A[i] == 2 || A[i] == 0) {
67
                                    // 新增一个 2
68
                                    if (b - 1 >= 0)
69
                                        cur = (cur +
70
                                               dp[pre][a][b - 1][c][d][e][f]) %
71
                                              MOD;
72
                                    // 与已有的 3 结合成 {3,2}，消耗 c，增加 f
73
                                    if (f - 1 >= 0)
74
                                        cur = (cur + 1ll *
75
                                                         dp[pre][a][b][c + 1][d]
76
                                                           [e][f - 1] *
77
                                                         (c + 1)) %
78
                                              MOD;
79
                                    // 与已有的 {1,3} 完成，消耗 e
80
                                    if (e < n)
81
                                        cur =
82
                                            (cur +
83
                                             1ll *
84
                                                 dp[pre][a][b][c][d][e + 1][f] *
85
                                                 (e + 1)) %
86
                                            MOD;
87
                                }
88
                                if (A[i] == 3 || A[i] == 0) {
89
                                    // 新增一个 3
90
                                    if (c - 1 >= 0)
91
                                        cur = (cur +
92
                                               dp[pre][a][b][c - 1][d][e][f]) %
93
                                              MOD;
94
                                    // 与已有的 1 结合成 {1,3}，消耗 a，增加 e
95
                                    if (e - 1 >= 0)
96
                                        cur = (cur + 1ll *
97
                                                         dp[pre][a + 1][b][c][d]
98
                                                           [e - 1][f] *
99
                                                         (a + 1)) %
100
                                              MOD;
101
                                    // 与已有的 {2,1} 完成，消耗 d
102
                                    if (d < n)
103
                                        cur =
104
                                            (cur +
105
                                             1ll *
106
                                                 dp[pre][a][b][c][d + 1][e][f] *
107
                                                 (d + 1)) %
108
                                            MOD;
109
                                }
110
                                dp[now][a][b][c][d][e][f] = cur % MOD;
111
                            }
112
    }
113
    cout << (dp[(3 * n) & 1][0][0][0][0][0][0] * calFac(n)) % MOD << endl;
114
}
115

116
signed main() {
117
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
118
    fac[0] = 1;
119
    int T;
120
    cin >> T;
121
    while (T--) {
122
        solve();
123
    }
124
    return 0;
125
}

音乐

音乐

P8366 [LNOI2022] 题#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

思路#

文章分享

音乐

安吉D1-G

P8366 [LNOI2022] 题#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

说明/提示#

思路#

文章分享