在CCPC网络赛上遇到由此改编的原题，然而并没有做出来….. 题意：给定一个n∗m 的矩阵，标记出其中的局部极小值，要求填入1…n∗m ，求方案数
Sample Input 2 4 .X.. …X 4 2 X. .. .. X. 1 2 XX
Sample Output Case #1: 2100 Case #2: 2520 Case #3: 0
由于局部极小值最多8 个，我们可以状压DP 令f i,j 表示已经填完了前i 个数，局部极小值的填充状态为j 的方案数 预处理出cnt j 表示填充状态为j 时共有多少位置是可以填充的(包括已填充的局部极小值位置) 那么有DP方程f i,j =f i−1,j ∗C 1 cnt j −i+1 +∑ k∈j f i−1,j−{k} 但是问题是这样虽然保证了标记的位置都是局部最小值，但是可能会导致一些未标记的位置成为局部极小值，因此我们枚举其他可以成为局部极小值的位置，容斥一下即可
时间复杂度O(DFS∗8nm∗2 8 )
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 12345678 using namespace std; const int dx[]={-1,-1,-1,0,0,1,1,1,0}; const int dy[]={-1,0,1,-1,1,-1,0,1,0}; int n,m,ans; char s[10][10]; int Calculate() { static pair<int,int> stack[10]; static int cnt[1<<8],f[30][1<<8]; int i,j,k,sta,top=0; memset(cnt,0,sizeof cnt); memset(f,0,sizeof f); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(s[i][j]=='X') stack[++top]=pair<int,int>(i,j); for(sta=0;sta<1<<top;sta++) { static bool unfilled[10][10]; memset(unfilled,0,sizeof unfilled); for(i=1;i<=top;i++) if(~sta&(1<<i-1)) unfilled[stack[i].first][stack[i].second]=true; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { for(k=0;k<9;k++) if(unfilled[i+dx[k]][j+dy[k]]) break; if(k==9) cnt[sta]++; } } f[0][0]=1; for(i=1;i<=n*m;i++) for(sta=0;sta<1<<top;sta++) { (f[i][sta]+=(long long)f[i-1][sta]*max(cnt[sta]-i+1,0))%=MOD; for(j=1;j<=top;j++) if(sta&(1<<j-1)) (f[i][sta]+=f[i-1][sta^(1<<j-1)])%=MOD; } return f[n*m][(1<<top)-1]; } void DFS(int x,int y,int cnt) { int i; if(y==m+1) { DFS(x+1,1,cnt); return ; } if(x==n+1) { (ans+=Calculate()*(cnt&1?-1:1))%=MOD; return ; } DFS(x,y+1,cnt); for(i=0;i<9;i++) if(s[x+dx[i]][y+dy[i]]=='X') break; if(i==9) { s[x][y]='X'; DFS(x,y+1,cnt+1); s[x][y]='.'; } } int main() { int i,j,k; cin>>n>>m; for(i=1;i<=n;i++) scanf("%s",s[i]+1); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(s[i][j]=='X') for(k=0;k<8;k++) if(s[i+dx[k]][j+dy[k]]=='X') return puts("0"),0; DFS(1,1,0); cout<<(ans+MOD)%MOD<<endl; }