其实原题就是【cqoi2012】【bzoj2669】局部极小值。 有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。 给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。
发现，X的位置最多有8个，那我们考虑状压dp。 我们从小到大把数填进去，用 fi,j 表示，把第i个数填进去后，每个X是否被填了数，用二进制数j表示。 预处理出 restj 表示填充状态为j时共有多少位置是可以填充的(包括已填充的局部极小值位置) 转移：
fi,j=fi−1,j∗(restj−(i−1))+∑k∈jfi−1,j−2k−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\n"); 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\n"); } if(ans!=-1) { dg(1,1,1); printf("%d\n",(ans%mo+mo)%mo); } } }