题意:题目非常长,前面讲了一大堆刚性的和灵活的,但是问的是网格图。很显然网格图不是刚性的(如下图),但是我们可以通过添加对角线使得它变为刚性的,问有多少种添加的方法使变为刚性的。
网格图
题解:可以(很难)发现,在摆动过程中,原来处于同一行的竖边一定平行;同理,原来处于同一列的横边一定平行。我们要做的即为所有横边垂直于所有竖边,那么一行和一列可以分别看做整体。更进一步地,如果两行竖边都垂直于同一列横边,这两行就属于同一个集合。
这里使用一个经典模型,将网格图的行和列作为二分图的左右两个点集,(x,y)连边就表示x行的竖边垂直于y列的横边,那么问题可以转化为最终n+m个点都连通的方案数。但是要注意,连边和添加对角线并不完全等价!添加对角线包含了主对角线和次对角线,而普通的连边没有这种含义。

我们设计一种动态规划(或者说递推),那它必然是总方案数减去不可行的方案数:
$$dp[n][m]=3^{nm}-\sum_{i=1,j=0}^{i<n||j<m} C_{n-1}^{i-1}C_{m}^{j}\cdot dp[i][j]\cdot 3^{(n-i)(m-j)}$$
$3^{nm}$表示对于每一个格子我们总是有无对角线,主对角线,次对角线三种选择。后面的减数项中,为了保证不重复,我们总是枚举左边明确的某一点(例如$1$号点)所在的连通块的左右大小。具体地,我们从$2-n$号点中选出$i-1$个,从$m$个点中选出$j$个,它们内部会有$dp[i][j]$种方案,至于剩下的$n-i$个点和$m-j$个点的关系,任意选择即可。

理解了之后写代码非常简单,可以用预处理做到$O(n^4)$

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=11;
const int MO=1e9+7;
ll C[N][N],dp[N][N],po3[N*N];

void init()
{
po3[0]=1;
for (int i=1;i<N*N;i++) {
po3[i]=po3[i-1]*3%MO;
}
C[0][0]=1;
for (int i=1;i<N;i++) {
C[i][0]=C[i][i]=1;
for (int j=1;j<i;j++) {
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MO;
}
}
for (int n=1;n<N;n++) {
for (int m=0;m<N;m++) {
dp[n][m]=po3[n*m];
for (int i=1;i<=n;i++) {
for (int j=0;j<=m;j++) {
if (i==n&&j==m) continue;
dp[n][m]-=C[n-1][i-1]*C[m][j]%MO*dp[i][j]%MO*po3[(n-i)*(m-j)]%MO;
dp[n][m]=(dp[n][m]%MO+MO)%MO;
}
}
}
}
}

int main()
{
init();
int n,m;
while (scanf("%d%d",&n,&m)!=EOF) {
printf("%lld\n",dp[n][m]);
}
return 0;
}