题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2669
题意概述：实际上原题意很简洁了我就不写了吧。。。。
二话不说先观察一下性质，首先棋盘很窄，可以乱搞的样子，然后注意到如果一个点是局部极小值那么周围3*3矩阵内不能有另一个局部最小值。于是画个图发现题目的数据范围最多有8个局部最小值。性质大概就是这些了。
暴力实际上是搜索，本质是多阶段决策问题。由于棋盘很小，容易让人联想到搞个插头dp之类东西来弄一下，依次填每个格子来作为一个决策阶段。然后就发现。。。这个东西太复杂了。。。等你想出来不知道什么时候去了（而且很有可能想不出来）。。。于是需要换个思路，把决策阶段改一下，每一行作为阶段的话更加复杂。。。弃疗。那么决策阶段很有可能就不是按照格子的顺序来的了。注意到局部最小值一定是周围的格子里面最小的那个，并且最多只有8个局部最小值，那么尝试从小到大填充每一个数字作为阶段，把局部最小值是否填充的状态压进去。
于是令f(s,i)表示用1~i的数字填充棋盘，集合s中的局部最小值已经被填充的方案数。
分析这种决策下的性质，发现一个局部最小值一定是以其为中心3*3内最先填的那个，也就是说如果一个局部最小值没有填充，那么周围3*3的点都不能填充。排除所有不可以填充的点剩下的就是可以填充的点，令cnt[s]表示局部极小值填充状态为s时的棋盘上最多有几个数字。
得到f(s,i)=f(s,i-1)*C(cnt[s]-i+1,1)+sum{ f(s-{j},i-1) | j是s的子集 }，时间复杂度O(N*M*X*2^X)，X表示棋盘上有多少个局部极小值。
但是可以注意到在状态设计的时候可以保证题目给出的X都成为局部最小值，但是可能让不是局部最小值的位置变成局部最小值。
于是这题最神的地方来了：容斥！由于棋盘很小，所以说打个回溯跑一下局部极小值的分布位置发现最多也就16000多的方案。我们用回溯跑出每一种题目要求位置为局部极小值的棋盘状态，对于每个状态来一次dp，然后根据有多少个额外的点是局部极小值进行奇偶容斥就得出答案。
时间复杂度O(O(容斥)*N*M*X*2^X)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=;
const int maxm=;
const int maxs=(<<)+;
const int mo=; int N,M,X,ans;
char mp[maxn][maxm];
struct XY{ int x,y; }p[];
int bin[],f[maxs][*+],cnt[maxs],vis[maxn][maxm],sz[maxs]; void data_in()
{
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++){
scanf("%s",mp[i]+);
for(int j=;j<=M;j++)
if(mp[i][j]=='X') p[++X]=(XY){i,j};
}
for(int i=;i<=;i++) bin[i]=<<i-;
for(int s=;s<bin[];s++) sz[s]=sz[s>>]+(s&);
}
void dp(int tot)
{
for(int s=;s<bin[tot+];s++){
cnt[s]=;
memset(vis,,sizeof(vis));
for(int j=;j<=tot;j++) if(!(bin[j]&s)){
int x=p[j].x,y=p[j].y;
vis[x-][y-]=vis[x-][y]=vis[x-][y+]=
vis[x][y-]=vis[x][y]=vis[x][y+]=
vis[x+][y-]=vis[x+][y]=vis[x+][y+]=;
}
for(int i=;i<=N;i++)
for(int j=;j<=M;j++) cnt[s]+=-vis[i][j];
}
memset(f,,sizeof(f));
f[][]=;
for(int i=;i<=cnt[];i++)
f[][i]=f[][i-]*(cnt[]-i+)%mo;
for(int s=;s<bin[tot+];s++)
for(int i=sz[s];i<=cnt[s];i++){
f[s][i]=f[s][i-]*(cnt[s]-i+)%mo;
for(int j=;j<=tot;j++) if(bin[j]&s)
f[s][i]=(f[s][i]+f[s^bin[j]][i-])%mo;
}
}
bool check(int x,int y) { return mp[x-][y-]!='X'&&mp[x-][y]!='X'&&mp[x-][y+]!='X'&&mp[x][y-]!='X'; }
void dfs(int x,int y,int n)
{
if(x>N){
dp(X+n);
if(n%==) ans=(ans+f[bin[X+n+]-][N*M])%mo;
else ans=(ans-f[bin[X+n+]-][N*M]+mo)%mo;
return;
}
int xx=x,yy=y+;
if(yy>M) xx++,yy=;
if(mp[x][y]=='X'){
if(check(x,y)) dfs(xx,yy,n);
}
else{
if(check(x,y)){
mp[x][y]='X',p[X+n+]=(XY){x,y};
dfs(xx,yy,n+);
mp[x][y]='.';
}
dfs(xx,yy,n);
}
}
void work()
{
dfs(,,);
printf("%d\n",ans);
}
int main()
{
data_in();
work();
return ;
}