P8366 [LNOI2022] 题
注意到 $n$ 很小。
合法的的划分中，三个数构成的逆序对数为奇数的三元组只有 $\{3, 2, 1\}, \{2, 1, 3\}, \{1, 3, 2\}$ ，统计划分时可以考虑记录 $\{1\}, \{2\}, \{3\}, \{1, 3\}, \{2, 1\}, \{3, 2\}$ 的数量，可以DP递推。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <cstdio>
#include <algorithm>
#define go(x) \
for (int a = 0; a <= min(x, n); ++a) \
for (int b = 0; a + b <= min(x, n); ++b) \
for (int c = 0; a + b + c <= min(x, n); ++c) \
for (int d = 0; a + b + c + d * 2 <= x && a + b + c + d <= n; ++d) \
for (int e = 0; a + b + c + d * 2 + e * 2 <= x && a + b + c + d + e <= n; ++e) \
for (int f = 0; a + b + c + d * 2 + e * 2 + f * 2 <= x && a + b + c + d + e + f <= n; ++f)
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 20, mod = 1e9 + 7;
int n;
void adj (int &x) { x += x >> 31 & mod; }
struct ModInt
{
int x;
ModInt (int _ = 0) { adj(x = _); }
int operator () () const { return x; }
ModInt& operator += (const ModInt &_) { adj(x += _.x - mod); return *this; }
ModInt& operator -= (const ModInt &_) { adj(x -= _.x); return *this; }
ModInt& operator *= (const ModInt &_) { x = (LL)x * _.x % mod; return *this; }
ModInt operator + (const ModInt &_) const { ModInt res = x; res += _; return res; }
ModInt operator - (const ModInt &_) const { ModInt res = x; res -= _; return res; }
ModInt operator * (const ModInt &_) const { ModInt res = x; res *= _; return res; }
} g[2][N][N][N][N][N][N];
int main ()
{
int T; read(T);
while (T--)
{
read(n);
go(n * 3)
g[0][a][b][c][d][e][f] = 0;
g[0][0][0][0][0][0][0] = 1;
for (int i = 1; i <= n * 3; ++i)
{
char ch = getchar();
while (ch > '9' || ch < '0') ch = getchar();
go(i)
g[i & 1][a][b][c][d][e][f] = 0;
go(i - 1)
{
ModInt &t = g[i - 1 & 1][a][b][c][d][e][f];
if (!t()) continue;
if (ch == '1' || ch == '0')
{
if (a + b + c + d + e + f < n) g[i & 1][a + 1][b][c][d][e][f] += t;
if (b) g[i & 1][a][b - 1][c][d][e + 1][f] += t * b;
if (f) g[i & 1][a][b][c][d][e][f - 1] += t * f;
}
if (ch == '2' || ch == '0')
{
if (a + b + c + d + e + f < n) g[i & 1][a][b + 1][c][d][e][f] += t;
if (c) g[i & 1][a][b][c - 1][d][e][f + 1] += t * c;
if (d) g[i & 1][a][b][c][d - 1][e][f] += t * d;
}
if (ch == '3' || ch == '0')
{
if (a + b + c + d + e + f < n) g[i & 1][a][b][c + 1][d][e][f] += t;
if (a) g[i & 1][a - 1][b][c][d + 1][e][f] += t * a;
if (e) g[i & 1][a][b][c][d][e - 1][f] += t * e;
}
}
}
ModInt res = g[n & 1][0][0][0][0][0][0];
for (int i = 1; i <= n; ++i) res *= i;
write(res()), puts("");
}
return 0;
}
|