局部极小值[cqoi2012]

发表于 分类于 ，

题意

有一个 $n$ 行 $m$ 列的整数矩阵，其中 $1$ 到 $nm$ 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（$8$ 连通）都小，我们说这个格子是局部极小值。

给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵，对 $12345678$ 取模。

$n\leq 4,m\leq 7$

题解

范围这么小，比较容易想到的是状压dp，设 $f_{i,S}$ 表示考虑到第 $i$ 个数，局部最小值中的数已经填上的状态是 $S$ 的方案数。

分类讨论一下是否填的是局部最小值的位置，预处理一下，然后转移即可。

时间复杂度 $O(2^{|S|}nm|S|)$。

但是好像有点不对，因为只保证了你钦定的点是极小值，你没钦定的也可能变成极小值。

于是容斥一下，枚举哪一些点可能成为极小值，由子集反演可知容斥系数为 $(-1)^{|T|-|S|}$

用 dfs 枚举，加上一些适当剪枝。

时间复杂度 $O(不会分析)$。

程序

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
#define P 12345678ll
#define LL long long
int fx[9] = {1,-1,0,1,-1,0,1,-1,0};
int fy[9] = {1,1,1,-1,-1,-1,0,0,0};
int n,m,top;
char s[10][10];
bool check(int x,int y){return x>0 && x<=n && y>0 && y<=m;}
struct Point{int x,y;};
Point a[10],st[30];
int g[260],f[30][260],tot;
bool bo[10][10];
LL ans;
LL dp()
{
	tot = 0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j] == 'X')
				a[tot++] = (Point){i,j};
	for(int sta = 0;sta<(1<<tot);sta++)
	{
		g[sta] = 0;
		for(int i=0;i<tot;i++) if(~sta&(1<<i)) bo[a[i].x][a[i].y] = true;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				int k;
				for(k=0;k<9;k++)
					if(check(i+fx[k],j+fy[k]) && bo[i+fx[k]][j+fy[k]]) break;
				if(k == 9) g[sta]++;
			}
		for(int i=0;i<tot;i++) if(~sta&(1<<i)) bo[a[i].x][a[i].y] = false;
	}
	memset(f,0,sizeof(f));
	f[0][0] = 1;
	for(int i=1;i<=n*m;i++)
		for(int sta=0;sta<(1<<tot);sta++)
		{
			f[i][sta] = f[i-1][sta] * max(g[sta]-i+1,0) % P;
			for(int j=0;j<tot;j++)
				if((1<<j)&sta)
					f[i][sta] = (f[i][sta]+f[i-1][sta^(1<<j)])%P;
		}
	return f[n*m][(1<<tot)-1];
}
void dfs(int now,int d)
{
	if(now > top) return void((ans += d*dp()%P+P)%=P);
	dfs(now+1,d);
	int x = st[now].x,y = st[now].y,k;
	for(k=0;k<9;k++)
		if(check(x+fx[k],y+fy[k]) && s[x+fx[k]][y+fy[k]] == 'X')
			break;
	if(k!=9) return;
	s[x][y] = 'X';
	dfs(now+1,-d);
	s[x][y] = '.';
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1,k;j<=m;j++)
		{
			for(k=0;k<9;k++) if(check(i + fx[k],j + fy[k]) && s[i+fx[k]][j+fy[k]] == 'X') break;
			if(k == 9) st[++top] = (Point){i,j};
		}
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}