题目大意：给定一个，求方案数
《多年的心头大恨终于切掉了系列》 考虑将数字从小到大一个一个填进去 由于局部极小值最多个，我们可以状压DP 令表示已经填完了前的方案数 预处理出时共有多少位置是可以填充的(包括已填充的局部极小值位置) 那么有DP方程 但是问题是这样虽然保证了标记的位置都是局部最小值，，但是可能会导致一些未标记的位置成为局部极小值，因此我们枚举其他可以成为局部极小值的位置，容斥一下即可
时间复杂度 其中最大为，足以通过所有数据
;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;}
微风吹过，海面上金光闪闪，泛起一道道美丽的浪花，
