Luogu 5023 - 填数游戏

这种找规律的题最不擅长了……

首先需要证明两个结论:

  1. 对角线单调不增

    这个结论应该是显然的,不妨假设对于两条路径,他们有着一段公共前缀,思考一下在分岔点需要注意什么就可以证明了,换而言之 $1$ 的存在必然是从左下开始的连续一段。

  2. 若 $(x - 1, y)$ 和 $(x, y - 1)$ 所填的数字相同,那么对于矩形 $(x, y)\rightarrow (n, m)$ ,有对于任意一条左上 $\rightarrow $ 到右下的对角线所填的数相等

    这个比较不好想,主要是情况略微复杂。考虑一个四方格(是一个矩阵的一个子矩阵):

    $x$ 表示随便填了,当然这两个 $1$ 可以一起换成 $0$ ,假设有两条路径,在到达这个子矩阵左上角的点时才进行分叉,分别是往右和往下,最后在这个子矩阵的右下角的点 $(x, y)$ 在此交汇。

    我们设路径 $1$ 先下降,即:$\mbox{DR}$,路径 $2$ 则是:$\mbox{RD}$ 。路径 $2$ 的字典序更大,故 $s_2 <= s_1$ 。易知倘若矩阵 $(x, y) \rightarrow (n, m)$ 存在任意一条对角线不是相同的,那么一定可以使 $s_2 > s_1$ 。

这两个结论证明完就可以进行 $\mbox{DP}$ 了,设 $f_{i, j, s}$ 表示从右下往左上数的第 $i$ 条对角线,有 $j$ 个 $1$ ,$s$ 是满足该点到 $(n, m)$ 的矩阵满足其任意对角线都相同的标号,标号按顺序标。

对于转移,枚举下一条对角线 $1$ 的个数,有且仅有一种合法的集合,计算出并进行转移。

打表可知,对于 $m > n + 1$ 时,有 $f_{n, m} = 3 \times f_{n, m - 1}$ ,直接进行转移。

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
#include <bits/stdc++.h>

#define MAXN 9

typedef long long lint;

using namespace std;

const int mod = 1e9 + 7;
int n, m, M;
int f[2][MAXN][1 << MAXN];
int len[MAXN << 1];

int right(int i, int x) {
return i <= m ? x : x + 1;
}

int down(int i, int x) {
return i <= m ? x - 1 : x;
}

lint power(lint a, int b) {
lint res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

int main() {
scanf("%d%d", &n, &m);
if (n == 1) {
printf("%lld\n", power(2, m));
return 0;
}
if (m > n + 1) {
M = m;
m = n + 1;
}
if (n > m)
swap(n, m);
int limit = n + m - 1;
for (int i = 1; i <= n; ++i)
len[i] = i;
for (int i = n + 1; i <= m; ++i)
len[i] = n;
for (int i = m + 1; i <= limit; ++i)
len[i] = limit - i + 1;
f[1][0][1] = f[1][1][1] = 1;
for (int i = 2; i <= limit; ++i) {
int c = i & 1;
memset(f[c], 0, sizeof(f[c]));
for (int j = 0; j <= len[i - 1]; ++j) {
for (int s = 0; s < (1 << len[i - 1]); ++s) {
if (!f[c ^ 1][j][s])
continue;
for (int k = 0; k <= len[i]; ++k) {
bool islegal = true;
for (int l = 1; l < len[i]; ++l)
if (l != k && !(s >> (right(i, l) - 1) & 1)) {
islegal = false;
break;
}
if (!islegal)
continue;
int t = 0;
for (int l = 1; l <= len[i]; ++l) {
int d = down(i, l), r = right(i, l);
if (!d)
t |= 1 << (l - 1);
else if (r > len[i - 1])
t |= 1 << (l - 1);
else if (d != j && (s >> (r - 1) & 1) && (s >> (d - 1) & 1))
t |= 1 << (l - 1);
}
f[c][k][t] = (f[c][k][t] + f[c ^ 1][j][s]) % mod;
}
}
}
}
int c = limit & 1;
lint ans = (f[c][1][0] + f[c][1][1] + f[c][0][0] + f[c][0][1]) % mod;
if (M)
ans = ans * power(3, M - m) % mod;
printf("%lld\n", ans);
}