HDU5838 Mountain

2016CCPC, HDU, 容斥, 状压DP

　　2016 CCPC网络赛

　　题意：给定n*m的方格及所有的局部最小值位置，放入数1－n*m，求可能的方案。 - 原题链接

　　赛时写了一发BFS，从小到大填数，填满局部最小值后乘上剩余方格数的阶乘，问题在于无法保证剩余方格数为非局部最小值。赛后才知道这是我CQOI2012原题，然而并没有做过＝ ＝
　　考虑这道题的规模可以状态压缩，总共25个数，最多9个局部最小值，用f[i][j]表示放入前i个数，所有局部最小值的状态为j时的总方案数。填数时预处理cnt[j]，计算出j状态下包括局部最小值在内的所有可放的格子数，状态转移可以表示为：

1
f[i][j]=f[i-1][j]*(cnt[j]-(i-1))+sig(f[i-1][j^(1<<k)])(j&(1<<k)==1)

　　要确保非局部最小值则需要枚举原状态下可能的局部最小值，容斥即可。因为自己写容斥比较少，整个程序学习的这篇博客，好像对容斥更理解了一点><
　　然而so sad，写了两天的程序，CQOI原题都AC了，却一直通不过杭电的数据T T
　　人生总是艰难，这游戏不想玩了，bug留到以后de吧… 


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
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define mp(a, b) (make_pair(a, b))
using namespace std;
const int maxn=5+10, maxm=(1<<10)+10, mod=772002;
typedef long long lint;
int ans, T, n, m, dd[9][2]={-1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1, 0, 0};
char mp[maxn][maxn];
bool Judge()
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) if(mp[i][j]=='X')
			for(int k=0; k<8; k++)
				if(mp[i+dd[k][0]][j+dd[k][1]]=='X')	return false;
	return true;
}
int DP()
{
	vector<pair<int, int> > vct;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) if(mp[i][j]=='X')
			vct.push_back(mp(i, j));
	int len=vct.size(), lim=(1<<vct.size()), tmp=n*m;
	int cnt[maxm]={0}, f[maxn*maxn][maxm]={0};
	for(int st=0; st<lim; st++)
	{
		bool u[maxn][maxn]={false};
		for(int i=0; i<len; i++)
			if(!(st&(1<<i))) u[vct[i].first][vct[i].second]=true;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)
			{
				bool f=true;
				for(int k=0; k<9&&f; k++) f&=!u[i+dd[k][0]][j+dd[k][1]];
				f&&(++cnt[st]);
			}
	}
	f[0][0]=1;
	for(int i=1; i<=tmp; i++)
		for(int st=0; st<lim; st++) 
		{
			f[i][st]=(f[i][st]+(lint)f[i-1][st]*max(cnt[st]-i+1, 0)%mod)%mod;
			for(int j=0; j<len; j++) if(st&(1<<j))
				f[i][st]=(f[i][st]+f[i-1][st^(1<<j)])%mod;
		}
	return f[tmp][lim-1];
}
void Dfs(int x, int y, int cnt)
{
	if(x==n+1)
	{
		ans=(ans+DP()*(cnt&1 ? -1 : 1)+mod)%mod;
		return ;
	}
	int tx=(y==m ? x+1 : x), ty=(y==m ? 1 : y+1);
	Dfs(tx, ty, cnt);
	for(int i=0; i<9; i++) if(mp[x+dd[i][0]][y+dd[i][1]]=='X')	return ;
	mp[x][y]='X';
	Dfs(tx, ty, cnt+1);
	mp[x][y]='.';
	return ;
}
int main()
{
	while(scanf("%d%d", &n, &m)!=EOF)
	{
		for(int i=1; i<=n; i++)	scanf("%s", mp[i]+1);
		if(!Judge())	printf("Case #%d: 0\n", ++T);
		else	ans=0, Dfs(1, 1, 0), printf("Case #%d: %d\n", ++T, ans);
	}
	return 0;
}