51Nod1634 刚体图

题意

计算机科学中,图可以看做是点集和边集所组成的二元组。通过给每个点设置一个平面坐标,图可以镶嵌在欧几里得平面中。
一个图被认为是刚体,如果该图无法只改变其中一部分的形状,而使得余下的部分的形状保持不变。
为了简化问题,我们现在只考虑$n \times m$的格点图。我们的问题是,对于$m \times n$的个点图,有多少种添加支撑的方案可以使其变为刚体?
注意本题在每个小矩形中,我们至多只允许添加一个方向的对角线。例如,对于$2 \times 3$的格点图,一共有$448$种方案。
$n,m \leqslant 100$。

题解

其实这道题最关键也是最精彩的地方就在于模型的转化。
考虑一个格点图是一个刚体,需要满足什么条件。其实你每往一个小矩形里加入一条对角线,就相当于强制要求某一横行的竖边,和某一竖行的横边垂直。题目的要求,是要让每一横行的竖边和每一竖行的横边都垂直。所以我们就可以把题目转化为,给出一个左边$n$个点,右边$m$个点的二分图。求使得这个二分图联通的方案数。此时可以考虑DP来做。
设$dp[i][j]$表示左边$i$个点,右边$j$个点所能形成的联通的二分图的方案数。直接计数不太好统计,我们考虑反向枚举,即统计有多少个不连通的。这个时候问题也就大大简化了。考虑枚举左边$1$号点所在的联通块,左边有多少个点,右边有多少个点,于是我们得到了如下的转移方程:
$$dp[i][j]=3^{ij}-\sum_{k=1}^i\sum_{l=0}^jC_{i-1}^{k-1}C_{j}^{l}dp[k][l]3^{(i-k)(j-l)}$$
理解起来不难,$k$和$l$分别表示$1$号点所在的联通块,左边右边分别的点数。先要从剩下的点里头选出这些点,再乘上这些点联通的方案数,再乘上其他点任意连的方案数即可。
时间复杂度$O(n^2m^2)$。不太懂51nod上为啥$n$和$m$只出到$10$……

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e2+10;
const int mod=1e9+7;
int dp[maxn][maxn],C[maxn][maxn],Pow3[maxn*maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline int fpm(int a,int b){
int ans=1;
while(b){
if(b & 1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;b/=2;
}
return ans;
}
inline int Mod(int val){
if(val>=mod)val-=mod;
if(val<0)val+=mod;
return val;
}
int main(){
int i,j,k,l,m,n,T;
#ifndef ONLINE_JUDGE
freopen("51Nod1634.in","r",stdin);
freopen("51Nod1634.out","w",stdout);
#endif
n=10;m=10;
C[0][0]=1;
Pow3[0]=1;
for(i=1;i<=n*m;i++)Pow3[i]=1ll*Pow3[i-1]*3%mod;
for(i=1;i<=n;i++){
C[i][0]=1;
for(j=1;j<=n;j++)
C[i][j]=Mod(C[i-1][j-1]+C[i-1][j]);
}
for(i=0;i<=n;i++)
for(j=0;j<=m;j++){
int &res=dp[i][j];res=Pow3[i*j];
for(k=1;k<=i;k++)
for(l=0;l<=j;l++){
if(k==i && j==l)continue;
res=Mod(res-1ll*Pow3[(i-k)*(j-l)]*dp[k][l]%mod*C[i-1][k-1]%mod*C[j][l]%mod);
}
}
while(scanf("%d%d",&n,&m)==2)printf("%d\n",dp[n][m]);
return 0;
}