BZOJ2669 [CQOI2012]局部极小值

题意

有一个$n$行$m$列的整数矩阵,其中$1$到$nm$之间的每个整数恰好出现一次。如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。
$1 \leqslant n \leqslant 4,1 \leqslant m \leqslant 7$。

题解

这道题初看范围让人浮想联翩,然而有一个问题让这道题没有那么容易,这个问题就是,不仅要使得那些告诉了你是局部极小值的点成为局部极小值,也要使得那些不是局部极小值的点一定要大于它旁边的某个数。一下子问题似乎复杂了不少。其实,对于这个问题,我们可以用一个容斥解决。具体来说,利用一个类似dfs的东西来计算,某些点一定是局部极小值,其他点无限制的方案数。于是我们的问题就得到了转化。接下来的部分,注意到局部极小值只有最多$8$个,于是我们考虑使用状压DP来解决。设$dp[i][j]$表示按照权值从小到大往表格中填数,填到数字$i$时,局部极小值填数的状态为$j$的方案数。那么我们可以先预处理一个cnt[]数组表示当前局部极小值填数状态为$i$时,可以填的非局部极小值的位置个数。那么我们有下面的转移方程:
如果我们这一次填的数不是局部极小值,那么我们有:
$$dp[i][j]=dp[i-1][j] \times (cnt[j]-i+1)$$
如果这一次填的数是局部极小值,那么有:
$$dp[i][j]=\sum_{k \in S}dp[i-1][j-2^k]$$
$S$表示$j$对应的集合。
然后就解决了。时间复杂度$O(dfs \times m \times n \times 2^8 \times 8)$,其中$dfs$大概是个几千的样子。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const double eps=1e-9;
const int mod=12345678;
const int maxn=5;
const int maxm=8;
int Flag[maxn][maxm],cnt[(1<<8)+10],vis[maxn][maxm],px[maxn*maxm],py[maxn*maxm];
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
ll dp[maxn*maxm][(1<<8)+10],ans;
int n,m;
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 ll calc(){
int i,j,k,top=0;
memset(cnt,0,sizeof(cnt));
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(Flag[i][j]){
px[++top]=i;py[top]=j;
}
int s=1<<top;
for(i=0;i<s;i++){
memset(vis,0,sizeof(vis));
for(j=1;j<=top;j++)
if(i & (1<<(j-1))){
for(k=0;k<=7;k++){
int posx=px[j]+dir[k][0],posy=py[j]+dir[k][1];
if(posx<=0 || posy<=0 || posx>n || posy>m)continue;
vis[posx][posy]=1;
}
vis[px[j]][py[j]]=1;
}
for(j=1;j<=n;j++)
for(k=1;k<=m;k++)
cnt[i]+=(1-vis[j][k]);
}
dp[0][0]=1;
for(i=1;i<=n*m;i++)
for(j=0;j<s;j++){
(dp[i][j]+=dp[i-1][j]*(cnt[j]-i+1))%=mod;
for(k=1;k<=top;k++)
if(j & (1<<(k-1)))
(dp[i][j]+=dp[i-1][j-(1<<(k-1))])%=mod;
}
return dp[n*m][s-1];
}
void dfs(int x,int y,int opt){
int i;
if(x==n+1){
(ans+=calc()*opt)%=mod;
return;
}
if(y==m)dfs(x+1,1,opt);
else dfs(x,y+1,opt);
int chk=!Flag[x][y];
for(i=0;i<=7;i++){
int posx=x+dir[i][0],posy=y+dir[i][1];
if(posx<=0 || posy<=0 || posx>n || posy>m)continue;
if(Flag[posx][posy])chk=0;
}
if(chk){
Flag[x][y]=1;
if(y==m)dfs(x+1,1,-opt);
else dfs(x,y+1,-opt);
Flag[x][y]=0;
}
}
int main(){
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("BZOJ2669.in","r",stdin);
freopen("BZOJ2669.out","w",stdout);
#endif
n=read();m=read();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
char ch=getchar();
while(ch!='.' && ch!='X')ch=getchar();
if(ch=='X')Flag[i][j]=1;
}
dfs(1,1,1);
printf("%lld\n",(ans%mod+mod)%mod);
return 0;
}