来自蒟蒻XXJ的做题记录
观察一下就知道里面最多会有8个X嘛== 然后就状压一下啊……
\(f[i][j]=f[i-1][j]*(cnt[s]-i+1)+f[i-1][j-(1<<p)]\)
PS:cnt[s] 表示一个填好的状态s下有多少个地方可以放数字i
来自dalao PoPoQQQ：
原来只考虑了保证标记的位置都是局部最小值
但是问题是这样虽然保证了标记的位置都是局部最小值，但是可能会导致一些未标记的位置成为局部极小值，因此我们枚举其他可以成为局部极小值的位置，容斥一下即可
所以正解是枚举每一种可能的局部最小值分布，用状压dp求出方案数，然后容斥（一步减，两步加）
#include<bits/stdc++.h>
using namespace std;
const int MOD=12345678;
int n,m,x[9],y[9],top,cnt[1<<9];
long long f[30][1<<9];
long long ans;
bool mm[6][9],wtm[6][9];
int dx[]={0,1,0,-1,1,-1,1,-1};
int dy[]={1,0,-1,0,1,-1,-1,1};
int dp(){
top=0;int s;memset(cnt,0,sizeof(cnt));
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(mm[i][j]){
x[++top]=i;y[top]=j;
}
s=1<<top;
for(int i=0;i<s;i++){
memset(wtm,0,sizeof(wtm));
for(int j=0;j<top;j++){
if(!((1<<j)&i)){
for(int k=0;k<8;k++){
int xx=x[j+1]+dx[k];
int yy=y[j+1]+dy[k];
if(xx<0||yy<0||xx>=n||yy>=m) continue;
wtm[xx][yy]=1;
}
wtm[x[j+1]][y[j+1]]=1;
}
}
for(int ni=0;ni<n;ni++)
for(int nj=0;nj<m;nj++) cnt[i]+=!(wtm[ni][nj]);
}
f[0][0]=1;
for(int i=1;i<=n*m;i++)
for(int j=0;j<s;j++){
f[i][j]+=(f[i-1][j]*(cnt[j]-i+1))%MOD;
f[i][j]%=MOD;
for(int p=0;p<top;p++){
if(!((1<<p)&j)) continue;
f[i][j]+=f[i-1][j-(1<<p)];
f[i][j]%=MOD;
}
}
return f[n*m][s-1];
}
void dfs(int nx,int ny,int z){
if(ny==m){dfs(nx+1,0,z);return;}
if(nx==n){
ans+=dp()*z;
ans%=MOD;
return;
}//Judge that the spot can be X or not Just Judge its round
dfs(nx,ny+1,z);
int judge(1);
for(int i=0;i<8;i++){
int xx=nx+dx[i];
int yy=ny+dy[i];
if(xx<0||yy<0||xx>=n||yy>=m) continue;
if(mm[xx][yy]) {judge=0;break;}
}
if(mm[nx][ny]) judge=0;
if(judge){mm[nx][ny]=1;dfs(nx,ny+1,z*(-1));mm[nx][ny]=0;}
}
void input(){
cin>>n>>m;
cin.get();
for(int i=0;i<n;i++){
char c[10];
scanf("%s",c);
for(int j=0;j<m;j++){
if(c[j]=='X') mm[i][j]=1;
else mm[i][j]=0;
}
}
}
void xxj(){
dfs(0,0,1);
}
void output(){
cout<<(ans+12*MOD)%MOD<<endl;
}
int main(){
input();
xxj();
output();
return 0;
}