题目
一眼就是状压，接下来就不知道了(qwq)
做法
我们能手玩出局部小值最多差不多是(8,9)个的样子，(dp_{i,j})为填满(1~i)数字，局部小值的状态为(j)
第(k)个局部极小值填(i)：(dp[i][j]=(dp[i][j]+dp[i-1][j^(1<<k-1)])%p)
不填在局部极小值，显然有些地方不能填(i)的，首先还没填的局部极小值不填，其周围也不能填(填(i)后后面再填比不符合局部极小值)
我们预处理出每种状态不能填时的位置：(dp[i][j]=(dp[i][j]+dp[i-1][j]*max(num[j]-i+1,0))%p)
一顿操作后发现WA了，我们得到的局部极小值可能不是恰好是给出的(X)(更多)
容斥原理：Ans=至少多0个极小值-至少多1个极小值+至少多两个极小值......
理解：至少多0个((x,x+1,x+2,x+3...)-k(x+1,x+2,x+3...))其中(k)为某些值的系数
填了至少多0个极小值后，有多填的部分那就得减去至少多1个极小值，至少多1个极小值的位置也有很多，就会有一些位置减掉的系数为(k>1)，就要又加上
(dfs)时加上能被多余的极小值填上的地方换成'X'，然后多次做(dp)
My complete code
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=31;
const int p=12345678;
const int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
int n,m,tot;
LL ans;
int x[maxn],y[maxn],num[1<<9],dp[maxn][1<<9];
bool visit[maxn][maxn];
char s[maxn][maxn];
inline int Solve(){
tot=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if (s[i][j]=='X')
x[++tot]=i,
y[tot]=j;
int Up=1<<tot;
for(int i=0;i<Up;i++){
int cnt(0);
memset(visit,0,sizeof(visit));
for(int j=1;j<=tot;++j)
if(!((i>>(j-1))&1)){
visit[x[j]][y[j]]=1;
for(int k=0;k<8;++k){
int xx=x[j]+dx[k];
int yy=y[j]+dy[k];
if(xx>0&&yy>0&&xx<=n&&yy<=m)
visit[xx][yy]=1;
}
}
for(int j=1;j<=n;++j)
for(int k=1;k<=m;++k)
if(visit[j][k])
++cnt;
num[i]=n*m-cnt;
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n*m;++i)
for(int j=0;j<Up;++j){
dp[i][j]=(dp[i][j]+dp[i-1][j]*max(num[j]-i+1,0))%p;
for(int k=1;k<=tot;k++)
if(j&(1<<(k-1)))
dp[i][j]=(dp[i][j]+dp[i-1][j^(1<<k-1)])%p;
}
return dp[n*m][Up-1];
}
void Dfs(int x,int y,int k){
if(y==m+1){
Dfs(x+1,1,k);
return;
}
if(x==n+1){
ans=(ans+(((k&1)==0)?1:-1)*Solve()+p)%p;
return;
}
Dfs(x,y+1,k);
if(s[x][y]!='X'){
bool f=true;
for(int i=0;i<8;i++)
if(s[x+dx[i]][y+dy[i]]=='X'){
f=false;
break;
}
if(f){
s[x][y]='X',
Dfs(x,y+1,k+1),
s[x][y]='.';
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf(" %s",s[i]+1);
Dfs(1,1,0);
printf("%lld
",ans);
return 0;
}
/*
5 5
.....
...X.
.X...
.....
....X
*/