题意
$给你一个n \times m(1\leq n,m \leq 10)的矩形,他由n \times m个单位矩阵组成$
$由于四边形具有不固定性,所以这个大矩形也是不固定的$
$现在让你加入一些斜着的边,问你多少种加的方案可以让他固定$
分析
- 最初我以为每行每列多加一个就可以把对应的行固定,可以这样想法太简单
- 这种思考的方式是错的,
> - 一个点固定一行是错的
> $这是在假设了除了当前行其他所有行都固定了$
> $然后发现一行一个点就能固定$
> $这错的,因为其他所有行都固定的情况下说明所有列也都被固定了,所有列固定了$
> $所有行自然也是固定的$
> - 已知一个点固定了$假设和他相连的点也是固定的,然后推出都是固定的$
> $如果不矛盾我就认为正确,这样推理假设方向反了,在这种情形下是不对的$
- 正确的思考方式是这样的
> - 一个点不能滑动有两种情况$:1.自己本身不能滑动,2.别人限制你滑动$
> $情况1不用讨论,现在讨论情况2.$
> $假设所有点不符合情况1的都能滑动$
> $那么如果假设与现实不矛盾或者如果能够找到一种滑动方案我就认为他能滑动$
- 上述思考方式对应的最基本的原型就是1*2的矩阵,一个被情况1固定,另一个不固定.这样属于符合上述假设所以能够滑动.
1\*2也许不容易思考.现在思考2\*2(同理衍生到3\*3等)的只有对角两个点被固定,他和上图中所给的情况是一样的,可以滑动,同时注意到n\*m的矩阵可以等效到2\*2上面,也就是左下角为确定固定的矩阵,右上角为确定固定矩阵,这时他们可以像2\*2一样滑动,为了阻止这种情况我们只需要在他们两个连接处任何一个位置添加一个就好因为这样就打破2\*2的滑动性,为了具有任意性也就是任意一个矩阵必须和他(等效后)斜对角矩形连通,进而转换成了**有多少种添加方式可以让某一个矩阵不被孤立**
孤立的条件是像2*2一样斜对角固定而两旁一个被固定的也没有->某一行某一列不能联通到其他所有行列->进而转换成连通图计数
这道题也可以这样联想,我们要固定矩形的任何一个子矩形
>1*1矩阵,固定他需要1个固定,1*2矩阵我们需要两个固定(且第二个放在新增加的行列上),2*2矩阵我们需要三个固定(且第三个放在新增加的行列上)…这样的模拟过程就是让新增的行列能够和之前联系也就是让所有行列连通
连通图计数传送门
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
|
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x << endl;
const int maxn = 4e5+100;
const int INF = 0x3f3f3f3f;
ll c[110][110];
ll base[110];
const int MOD = 1e9+7;
void calc(){
c[1][0] = 1;c[1][1] = 1;
for(int i = 2; i <= 100; ++i){
c[i][0] = 1;
for(int j = 1; j <= i; ++j){
c[i][j] = (c[i-1][j-1]+c[i-1][j])%MOD;
}
}
base[0] = 1;
for(int i = 1; i <= 100; ++i){
base[i] = (base[i-1]<<1)%MOD;
}
}
ll dp[11][11][110];
void slove(){
memset(dp, 0, sizeof dp);
c[0][0] = 1;
dp[1][0][0] = dp[0][1][0] = 1;
for(int i = 1; i <= 10; ++i){
for(int j = 1; j <= 10; ++j){
if(i==1||j==1){
dp[i][j][i+j-1] = 1;
continue;
}
for(int k = 1; k <= i*j; ++k){
dp[i][j][k] = c[i*j][k];
for(int ii = 0; ii <= i; ++ii){
for(int jj = 0; jj <= j; ++jj){
if(i+j==ii+jj) continue;
for(int kk = 0; kk <= k; ++kk){
ll ret = c[i-1][ii-1]*c[j][jj]%MOD;
ret = ret*dp[ii][jj][kk]%MOD;
ret = ret*c[(i-ii)*(j-jj)][k-kk]%MOD;
dp[i][j][k] = (dp[i][j][k]-ret+MOD)%MOD;
}
}
}
}
}
}
}
ll pow(ll x, ll y){
ll ans = 1;
while(y){
if(y&1) ans = ans*x%MOD;
x = x*x%MOD;
y >>= 1;
}
return ans;
}
int main(){
#ifdef LOCAL
freopen("/home/zeroxf/桌面/in.txt","r",stdin);
#endif
int n, m;
calc();
slove();
while(scanf("%d%d", &n, &m) != EOF){
ll ans = 0;
for(int i = 0; i <= n*m; ++i){
ans = (ans+base[i]*dp[n][m][i])%MOD;
}
printf("%lld\n",ans);
}
return 0;
}
|