题目
分析
其实原题就是【cqoi2012】【bzoj2669】局部极小值。
有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。
给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。
发现，X的位置最多有8个，那我们考虑状压dp。
我们从小到大把数填进去，用(f_{i,j})表示，把第i个数填进去后，每个X是否被填了数，用二进制数j表示。
预处理出(rest_j)表示填充状态为j时共有多少位置是可以填充的(包括已填充的局部极小值位置)
转移：
[f_{i,j}=f_{i-1,j}*(rest_j-(i-1))+sum_{kin{j}}f_{i-1,j-2^{k-1}}
]
但是有些不是为X的位置有可能也是局部极小值，那么我们用容斥，每次把一下有可能出现局部极小值的地方改为X，当额外增加的X的个数为奇数，ans就减去dp得所得的答案，否则ans加上dp得所得的答案。
其中dp方面这篇论文（第5页到第8页）讲的非常清楚
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=12345678;
const int N=10;
int z[9][2]=
{
{-1,-1},
{-1,0},
{-1,1},
{0,-1},
{0,1},
{1,-1},
{1,0},
{1,1},
{0,0}
};
int a[N][N],T,n,m,ans,f[N*N][2000],mi[10],sign[N][2],tot,rest[2000];
char c[N][N];
bool bz[N][N];
int val()
{
tot=0;
int state=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(c[i][j]=='X')
{
state+=mi[tot];
sign[++tot][0]=i;
sign[tot][1]=j;
}
}
for(int i=0;i<=state;i++)
{
memset(bz,true,sizeof(bz));
rest[i]=0;
for(int j=1;j<=tot;j++)
if((mi[j-1]&i)==0)
{
for(int k=0;k<=8;k++)
{
bz[sign[j][0]+z[k][0]][sign[j][1]+z[k][1]]=false;
}
}
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
{
if(bz[j][k])
rest[i]++;
}
}
f[0][0]=1;
for(int i=1;i<=n*m;i++)
for(int j=0;j<=state;j++)
{
f[i][j]=0;
(f[i][j]+=f[i-1][j]*(rest[j]-i+1)%mo)%=mo;
for(int k=1;k<=tot;k++)
{
if(mi[k-1]&j)
{
(f[i][j]+=f[i-1][j-mi[k-1]])%=mo;
}
}
}
return f[n*m][mi[tot]-1];
}
int dg(int x,int y,int z1)
{
if(x>n)
{
(ans+=(val()*(z1%2?1:-1))%mo)%mo;
return 0;
}
int xx=x,yy=y+1;
if(yy>m)
{
yy=1;
xx++;
}
dg(xx,yy,z1);
bool q=true;
for(int i=0;i<=8;i++)
{
if(c[x+z[i][0]][y+z[i][1]]=='X')
{
q=false;
break;
}
}
if(q)
{
c[x][y]='X';
dg(xx,yy,z1+1);
c[x][y]='.';
}
}
int main()
{
mi[0]=1;
for(int i=1;i<=9;i++)
mi[i]=mi[i-1]*2;
scanf("%d",&T);
while(T--)
{
tot=0;
ans=0;
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c[i][j]=getchar();
while(c[i][j]!='X' && c[i][j]!='.')
c[i][j]=getchar();
if(c[i][j]=='.')
tot++;
}
}
if(tot==n*m)
{
printf("0
");
continue;
}
for(int i=1;i<=n && ans!=-1;i++)
{
for(int j=1;j<=m;j++)
{
bool q=true;
if(c[i][j]=='X')
for(int k=0;k<=7;k++)
{
if(c[i+z[k][0]][j+z[k][1]]=='X')
{
q=false;
ans=-1;
break;
}
}
if(!q)
{
ans=-1;
break;
}
}
}
if(ans==-1)
{
printf("0
");
}
if(ans!=-1)
{
dg(1,1,1);
printf("%d
",(ans%mo+mo)%mo);
}
}
}