题目描述详见 luogu

题目可以说是非常的长,但是读懂之后概括一下大概就是找到一种填写01的方式,使得任意取两条合法(从$(1,1)$向右向下走到右下角)的路径, 右上路径经过的数字连接成的字符串字典序小。

然后就是漫长的手模+找规律

在模拟$3*3$时,第一次模拟出来的结果非常amazing,竟然有144种
在我的理解中,我认为只要是左下-右上走向的线上的数字不递增就可以了
如图

如图$4 \times 4 \times 3 \times 3=144$

但是显然 这是错误的

正确解法:

对于上面我的那种天真的想法,这就是一个反例

这种交叉的情况下,就要分类讨论

1.当$n=1$时:

很明显,答案是$m^{2}$ 这里就不多讨论了。

2.当$n>1$ 且 $n=m$时

($n = 3$)

图中橙色数字为这一平行线的可能数量, 红色为填入的数字, 蓝色为平行线, 蓝色区域填入的数字必须相等,否则会导致交叉情况出错

($n = 4$)

……

会发现

$$
ans(3,3) = 2^2 \times 3 \times 4 + 2^4 \times 4 \
ans(4,4) = 2^5 \times 5+2^4\times3\times5+2^5\times4^2\
ans(5,5) = 2^7\times4\times5+2^5\times3\times5+2^6\times4^3
$$

可得

$$
ans (n,n) = 2^3\cdot ans(n-1, n-1)-5\times2^n
$$

3.当 $n>1$ 且 $n+1=m$时

$$
ans(n,n+1)=3\cdot ans(n,n) - 3\times 2^n
$$

4.当$n>1$且$n+1<m$

$$
ans(n,i)=3\cdot ans(n,i−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
#include <bits/stdc++.h>

using namespace std;

int n, m, mod = 1000000007, f[10];
long long ans;

int main()
{
cin >> n >> m;
f[1] = 2;
for (int i = 2; i <= 8; i++)
f[i] = f[i-1] * 2;
if (n > m) swap(n, m);
if (n == 1){
ans=1;
for (int i = 1; i <= m; i++)
ans = ans * 2 % mod;
cout << ans << endl;
return 0;
}
else
if (n == 2) ans = 12;
else
if (n == 3) ans = 112;
else
if (n == 4) ans = 912;
else{
ans = 912;
for (int i = 5; i <= n; i++)
ans = ans * 8 - 5 * f[i];
}
if (m == n + 1 && n > 3)
ans = ans * 3 - 3 * f[n];
else
if (m == n + 1) ans = ans *3;

if (m > n + 1)
{
if (n > 3)
ans = ans *3 - 3 * f[n];
else
ans = ans *3;
for (int i = n + 2; i <= m; i++)
ans = ans * 3 % mod;
}

cout << ans << endl;
return 0;
}

(敲完人没了,这比T3还恶心

评论