整体上是两句话

• 每个关键点比其临集点先选
• 每个非关键点不比其临集点后选

Part1

设关键点集合为$S$

答案就是求$f(S)$恰好只有$S$集合比其临集点先选

再设$g(S)$至少有$S$集合比其临集点先选

$f(S)=\sum\limits_{S\subseteq T}(-1)^{|T|-|S|}g(T)$

你整体上做一个容斥，枚举非关键点的选择情况即$T\oplus S$,求出$g(T)$

Part2

做dp的整体思路是按照数的大小从小到大放，假设已经放的关键点集合是$S$,设$g_{i,S}$表示放了$[1,i]$这些数，关键点集合为$S$

对已经定的$S$，我们先预处理出对其每个子集$S'$的$h(S')$表示邻集不包含除了这个子集外任何其他关键点的非关键点个数

则我们以关键点集合为分层做层间和层内dp

• $f_{i-1,S}\cdot \max\{h(S)-i+1,0\}\to f_{i,S}$
• $f_{i-1,S}\to f_{i,S\oplus sta_j}$

#include<bits/stdc++.h>
#define mod 12345678
using namespace std;
int n,m,ans,cnt,g[1<<9],f[29][1<<9],dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};
char s[5][8];
struct Node{int x,y;}p[10];
inline int DP(void){
	int i,j,k,d,flag;
	for(cnt=0,i=1;i<=n;++i)
		for(j=1;j<=m;++j)if(s[i][j]=='X')p[++cnt]={i,j};
	for(i=0;i<1<<cnt;++i){
		for(j=1;j<=cnt;++j)s[p[j].x][p[j].y]=((i>>(j-1))&1)?'.':'X'; 
		for(g[i]=0,j=1;j<=n;++j)
			for(k=1;k<=m;++k)if(s[j][k]=='.'){
				for(flag=1,d=0;d<8;++d)if(s[j+dx[d]][k+dy[d]]=='X'){flag=0;break;}
				g[i]+=flag;
			}
	}for(i=1;i<=cnt;++i)s[p[i].x][p[i].y]='X'; 
	for(f[0][0]=i=1;i<=n*m;++i)
		for(j=0;j<1<<cnt;++j){
			for(f[i][j]=1ll*f[i-1][j]*max(0,g[j]-i+1)%mod,k=1;k<=cnt;++k)if((j>>(k-1))&1)f[i][j]=(f[i][j]+f[i-1][j-(1<<(k-1))])%mod;
		}
	
	return f[n*m][(1<<cnt)-1];
}
inline void dfs(int x,int y,int dlt){
	int tx,ty,i;
	if(x>n)return void(ans=(ans+1ll*dlt*DP())%mod);
	if(y==m)tx=x+1,ty=1;else tx=x,ty=y+1;
	dfs(tx,ty,dlt);if(s[x][y]=='.'){for(i=0;i<8;++i)if(s[x+dx[i]][y+dy[i]]=='X')return ;s[x][y]='X',dfs(tx,ty,mod-dlt),s[x][y]='.';}
}
signed main(void){
	int i;scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)scanf("%s",s[i]+1);
	printf("%d\n",(dfs(1,1,1),ans));
	return 0;
}