非常有趣的题目。
首先观察样例，不妨猜测蛇一定是对称的（这点我们稍后证明）。因此我们可以将这个正方形砍掉一半只保留左上角。
考虑对角线上的点，每个点必然不同的蛇。这是因为一条蛇只能往右侧和下方走，所以一条蛇不可能同时占有一个格子和一个格子右上角的格子。
因此，我们考虑为每个对角线上的格子分配一个长度，其对应的棋盘结果是唯一的。因为你只能贴着边界摆放。
比如考虑这张图，如果这样摆放，那么 两个点就成为了孤立点，之后没有摆放的办法了。
因为 点无论是向右侧的路还是向下的路都被堵住了，没办法到达对角线上。因而之后不可能有经过 中任意一点的蛇接触到对角线，和我们对角线上的点唯一对应一条蛇矛盾。
另外这种方式放置永远是合法的。证明比较复杂（而且之后有更简洁的版本），大致说一下证明思路。
考虑第一条蛇最终蛇头在 ，那么相当于禁止了后面所有的蛇蛇头停在左下角的格子（也就是 ）。考虑蛇的身子经过了一个被禁止格子的情况，不难发现此时这个格子要么是拐点要么是竖直的部分（并排的两个禁止格子不可能，因为左侧格子在下方空着的情况下是无法到达的），相当于把禁止的格子向左下方移动了一个格子。
另外，用这种方式也可以证明放置完前 条蛇之后的形状和前 条蛇的选择方案唯一对应。另外，如果你把轮廓线提取出来，向右侧表示 ，向下表示 最后得到一个二进制数，如果从低到高第 位是 ，那么前 条蛇里就选择了长度为 的蛇。
但是你发现这种思路并没有什么前途。因为很难处理已经给出了若干条蛇的限制的情况。我们不妨换个角度。
之前提到“一条蛇不可能同时占有一个格子和一个格子右上角的格子”，那么除了对角线上的点， 上的点也对应不同的蛇。
比如下面这张图中描出来的点就对应着不同的蛇，并且对应的是所有长度至少为 的蛇（因为长度为 的蛇够不到这条线）。
下面为了看的更清楚，我们不妨将这个正方形旋转 度变成一个金字塔。
考虑任意一组合法的方案。
你会发现，每一行会增加一个新的蛇头。不是蛇头的位置，一定会往左上方或者右上方连边（对应我们之前的结论）。
并且，一旦确定了蛇头的位置，其余位置的连边方向也确定了（左侧的蛇只能往右上连边，右侧的蛇只能往左上连边），和上一行的连接方式无关。
而一开始给定的若干条蛇，就是给一些格子钦定了往左侧连边，还是往右侧连边，还是作为蛇头。
我们直接枚举一下每一行有哪些位置可以作为蛇头，最后将每一行的方案数乘起来即可。
判断一个位置是否可以作为蛇头的方法是，看看是否左侧的所有格子都可以向着右上角连边，看看右侧的所有格子是否可以向着左上角连边，可以拿个 bool 数组维护一下前后缀信息。
最后考虑最开始的对称性证明。
我们不妨把蛇从长到短标号，最长的记作 ，最短的记作 。对于任意一组方案，对于每个格子记下经过这个格子的蛇的编号。显然方案和表格是一一对应的。
考虑第一行和最后一行。显然必须都是 ，因为只有这样长度才能是 。
考虑第二行和倒数第二行，不妨假设第二行的标号序列是 。由于放下的蛇不能交叉，而蛇又是连续的，因此如果倒数第二行 的位置不是 ，那么中间必然产生了交叉。因此第二行和倒数第二行的标号序列都是 。
同理可证第三行，第四行的标号序列都一样。
因此上下半区表格是对称的，最后的方案自然也是对称的。
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
| #include <iostream>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
private:
uint_type x;
void norm() { x -= mod * (x >= mod); }
public:
modular() : x(0) {}
modular(int_type _x) {
if (_x < 0) {
x = _x % (int_type)mod + (int_type)mod;
}
else {
x = _x % mod;
}
norm();
return;
}
friend modular operator+(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + rhs.x;
ret.norm();
return ret;
}
friend modular operator-(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + mod - rhs.x;
ret.norm();
return ret;
}
friend modular operator*(const modular &lhs, const modular &rhs) {
return modular(lhs.x * rhs.x);
}
modular operator-() const {
modular ret;
ret.x = mod - x;
return ret;
}
modular operator-=(const modular &b) { return *this = *this - b; }
modular operator+=(const modular &b) { return *this = *this + b; }
modular operator*=(const modular &b) { return *this = *this * b; }
bool operator==(const modular &b) const { return x == b.x; }
uint_type val() const { return x; }
friend std::istream &operator>>(std::istream &is, modular &rhs) {
is >> rhs.x;
rhs.x %= mod;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
os << rhs.val();
return os;
}
};
using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
}
namespace solve {
const uint mod = 1e9 + 7;
using mll = maths::modint1000000007;
bool check_par(const std::vector<std::pair<uint, uint>> &v, uint n) {
uint mid = v.size() / 2;
if (n - 1 - v[mid].first != v[mid].second) {
return false;
}
uint last = v.size();
for (size_t i = 0; i < mid; i++) {
if (n - v[i].first - 1 + n - 1 - v[last - 1 - i].first !=
v[i].second + v[last - i - 1].second) {
return false;
}
}
return true;
}
void solve() {
uint n, k;
std::cin >> n >> k;
std::vector<std::vector<std::pair<uint, uint>>> cur(k);
bool all_par = true;
std::vector<std::vector<uint>> skmap(n, std::vector<uint>(n));
for (size_t i = 0; i < k; i++) {
uint x, y, len;
std::cin >> len >> x >> y;
--x, --y;
cur[i].reserve(len);
cur[i].push_back({x, y});
std::string s;
if (len != 1) std::cin >> s;
skmap[x][y] = 1;
for (auto &&c : s) {
if (c == 'R') {
++y;
skmap[x][y] = 3;
}
else {
++x;
skmap[x][y] = 2;
}
cur[i].push_back({x, y});
}
all_par &= check_par(cur[i], n);
}
if (!all_par) {
std::cout << "0\n";
return;
}
std::vector<mll> dp(n);
dp[0] = 1;
for (size_t i = 1; i < n; i++) {
std::vector<uint> layer_stat(i + 1);
for (size_t j = 0; j <= i; j++) {
layer_stat[j] = skmap[i - j][j];
}
std::vector<bool> vaild_prefix(i + 2), vaild_suffix(i + 2);
vaild_prefix[0] = true;
vaild_suffix.back() = true;
for (size_t j = 0; j <= i; j++) {
vaild_prefix[j + 1] =
vaild_prefix[j] && (layer_stat[j] == 0 || layer_stat[j] == 2);
}
for (int j = i; j >= 0; j--) {
vaild_suffix[j] = vaild_suffix[j + 1] &&
(layer_stat[j] == 0 || layer_stat[j] == 3);
}
uint cnt = 0;
for (size_t j = 0; j <= i; j++) {
if ((layer_stat[j] == 0 || layer_stat[j] == 1) && vaild_prefix[j] &&
vaild_suffix[j + 1]) {
cnt++;
}
}
dp[i] = cnt * dp[i - 1];
}
std::cout << dp.back() << std::endl;
}
}
int main() {
uint t;
std::cin >> t;
while (t--) {
solve::solve();
}
std::cout << std::flush;
return 0;
}
|