Description

抽象题意：在一个矩阵中依次填入数，要求只有规定的数是小于它周边的数。

Solution

先来考虑一下当每一个.都有与它相邻的X， 因为棋盘很小，最多有8个X， 用状态压缩： fi,S 表示当前选到数字i，状态为S，

fi,S=fi−a,S∗(RS−i+1)+∑k∈Sfi−1,K RS 表示在i的状态下，总共有多少个位置可以填， 我们发现，这样会算重，所有要用容斥原理来做， 复杂度： O(2m1∗2k∗nm) ，k表示有多少个X，m1表示可以填的位置数；

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define OK(q,w) ((q)>0&&(w)>0&&(q)<=n&&(w)<=m) using namespace std; typedef long long LL; const int N=10,mo=12345678; int m,n,ans,m1; int a[N][N]; LL R[1<<10]; LL f[N*N][1<<10]; int er[21]; bool z[N][N],z1[N][N]; int fx[8][2]={{-1,0},{-1,-1},{0,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1}}; bool OKX(int i,int j,int e) { fo(k,0,e)if(OK(i+fx[k][0],j+fx[k][1]))if(a[i+fx[k][0]][j+fx[k][1]])return 1; return 0; } int doit() { fo(I,0,er[m1+1]-1) { R[I]=0; fo(i,1,n)fo(j,1,m) { bool z=1; fo(k,0,7)if(OK(i+fx[k][0],j+fx[k][1])) if(a[i+fx[k][0]][j+fx[k][1]]&&!(er[a[i+fx[k][0]][j+fx[k][1]]]&I))z=0; if(((er[a[i][j]]&I)||!a[i][j])&&z)R[I]++; } } f[0][0]=1; fo(i,1,n*m) fo(I,0,er[m1+1]-1) { LL t=0; fo(j,1,m1)if(er[j]&I)t=(t+f[i-1][I-er[j]])%mo; f[i][I]=(f[i-1][I]*(R[I]-i+1)%mo+t)%mo; } return f[n*m][er[m1+1]-1]; } void ss(int q,int w,int e) { if(w>m)q++,w=1; if(q>n){ans=(ans+doit()*((e%2)?-1:1))%mo;return;} ss(q,w+1,e); if(!a[q][w]&&!z[q][w]&&z1[q][w]) { a[q][w]=++m1; z1[q+1][w-1]=z1[q+1][w]=z1[q+1][w+1]=0; ss(q,w+2,e+1); a[q][w]=0;m1--; z1[q+1][w-1]=z1[q+1][w]=z1[q+1][w+1]=1; } } int main() { int q,w,_; er[1]=1;fo(i,2,20)er[i]=er[i-1]<<1; scanf("%d",&_); while(_--) { scanf("%d%d",&n,&m); m1=0; fo(i,1,n) fo(j,1,m) { char ch=' ';a[i][j]=0; while(ch!='.'&&ch!='X')ch=getchar(); if(ch=='X')a[i][j]=++m1; } fo(i,1,n)fo(j,1,m) { z1[i][j]=!(z[i][j]=OKX(i,j,7)); if(a[i][j]&&z[i][j])m1=0; } if(!m1){printf("0\n");continue;} ans=0; ss(1,1,0); printf("%lld\n",(ans+mo)%mo); } return 0; }