P3160 [CQOI2012] 局部极小值

注意到地图上最多能放 \(8\) 个局部极小值，考虑 \(dfs\) 出所有放置局部极小值的地图，输入中给定的局部极小值的点再这个地图中也一定是局部极小值，其它不管。
在当前地图中，我们定义局部极小值点为这个点在这张地图中必须成为局部极小值。
然后对这个图做 \(dp\)，设 \(f_{i,j}\) 表示从小到大填数，填到 \(i\)，局部极小值的放置状态为 \(j\) 的方案数，一个点如果周围没有还未放置的局部极小值点或者祂就是局部极小值点，那么可以放置，反之不行。可以预处理一下每个状态可以放置数字的非局部极小值点的点的数量，然后直接转移。
发现这样 \(dp\) 是保证了局部极小值点一定为局部极小值，但没报正其祂点不是局部极小值，所以可以用容斥，这是开头提到的 \(dfs\) 就派上用场了。
时间复杂度不知道，但跑的飞快。

代码

/*
Luogu P3160 [CQOI2012] 局部极小值
2026-03-18
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{
    int z;
    Modint(){z=0;}
    Modint(int x){x%=mod;z=x<0?x+mod:x;}
    Modint(long long x){x%=mod;z=x<0?x+mod:x;}
    Modint(short x){x%=mod;z=x<0?x+mod:x;}
    Modint(char x){x%=mod;z=x<0?x+mod:x;}
    Modint(bool x){x%=mod;z=x<0?x+mod:x;}
    friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}
    friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}
    friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}
    Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}
    Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}
    Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}
    Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}
    Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}
    Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}
    Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}
    friend Modint ksm(Modint a,int b){
        Modint ans=1;
        while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}
        return ans;
    }
    friend void read(Modint&z){
        int x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();
        f?x=-x:0;
        z.z=x;
    }
    friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int maxn=10,mod=12345678;
#define M Modint<mod>
int n,m,fx[10]={0,0,0,1,1,1,-1,-1,-1},fy[10]={0,1,-1,0,1,-1,0,1,-1},id[maxn][maxn];
bool is[maxn][maxn];
M ans,f[maxn*maxn][1000],g[1000];
M calc(){
    int cnt_id=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(is[i][j]) id[i][j]=++cnt_id;else id[i][j]=0;
    for(int i=0;i<(1<<cnt_id);i++){
        g[i]=0;
        for(int x=1;x<=n;x++) for(int y=1;y<=m;y++){
            if(is[x][y]) continue;
            bool can=1;
            for(int j=1;j<=8;j++){
                int xx=x+fx[j],yy=y+fy[j];
                if(is[xx][yy]&&!(i&(1<<id[xx][yy]-1))) can=0;
            }
            g[i]+=can;
        }
    }
    f[0][0]=1;
    for(int i=1;i<=n*m;i++) for(int j=0;j<(1<<cnt_id);j++){
        if(g[j].z-i+1+__builtin_popcount(j)>0) f[i][j]=f[i-1][j]*(g[j]-i+1+__builtin_popcount(j));
        else f[i][j]=0;
        for(int k=1;k<=cnt_id;k++){
            if(!(j&(1<<k-1))) continue;
            f[i][j]+=f[i-1][j^(1<<k-1)];
        }
    }
    return f[n*m][(1<<cnt_id)-1];
}
void dfs(int x,int y,int g){
    if(x==n+1){
        if(g&1) ans-=calc();
        else ans+=calc();
        return ;
    }
    int ntx=x,nty=y;
    nty++;
    if(nty==m+1) nty=1,ntx++;
    if(is[x][y]) return dfs(ntx,nty,g);
    dfs(ntx,nty,g);
    for(int i=1;i<=8;i++){
        int xx=x+fx[i],yy=y+fy[i];
        if(is[xx][yy]) return ;
    }
    is[x][y]=1;
    dfs(ntx,nty,g+1);
    is[x][y]=0;
}
signed main(){
    read(n,m);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        char x;read(x);
        if(x=='X') is[i][j]=1;
    }
    dfs(1,1,0);
    write(ans);
    return 0;
}