Input
N个花园的形态
Output
对于每个花园，输出形态
Sample Input
2
3 2
X.
..
.X
2 2
X.
..
Sample Output
60
6
Solution
可以发现最多只能有8个X，所以就状压这8个X就行了
f[i][s]表示当前涂了i个数，X的状态为s的方案数
rest[s]表示状态s可以放的点数
但这只能得三十分，因为题目描述说只有X小于
而除了那额外的三十分，都可能算重，那就容斥随便搞搞
Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define mo 12345678
#define ll long long
using namespace std;
int n,m,q,a[6][9],b[6][9],bz[6][9],sb[30],rest[256],d[30][2],tot,o[9]={0,0,0,1,1,1,-1,-1,-1},p[9]={0,1,-1,1,0,-1,1,0,0-1};
ll f[30][256],ans;
ll wtf(int x)
{
x+=q;
f[0][0]=1;
fo(s,0,(1<<x)-1)
{
memset(bz,0,sizeof(bz));int k=0;rest[s]=n*m;
fo(i,1,n) fo(j,1,m)
if(a[i][j]==1)
{
k++;
if((s&(1<<(k-1)))==0) fo(k,0,8) if(i+o[k]>0&&i+o[k]<=n&&j+p[k]>0&&j+p[k]<=m)rest[s]-=(1-bz[i+o[k]][j+p[k]]),bz[i+o[k]][j+p[k]]=1;
}
}
fo(i,1,n*m) fo(s,0,(1<<x)-1)
{
f[i][s]=(f[i-1][s]*(ll)(rest[s]-i+1))%mo;
fo(j,1,x) if(s&(1<<(j-1))) f[i][s]=(f[i][s]+f[i-1][s-(1<<(j-1))])%mo;
}
return f[n*m][(1<<x)-1];
}
void dg(int x,int z)
{
if(x>tot){if(z%2==1) ans=(ans-wtf(z)+mo)%mo;else ans=(ans+wtf(z))%mo;return;}
dg(tot+1,z);
fo(i,x,tot) if(sb[i]==0)
{
int q=0,h=d[i][0],j=d[i][1];
sb[i]=1;a[h][j]=1;
fo(k,0,8) if(a[h+o[k]][j+p[k]]==0) q++;
if(q==8)dg(i+1,z+1);
sb[i]=0;a[h][j]=0;
}
}
int main()
{
int ac;
for(scanf("%d\n",&ac);ac;ac--)
{
scanf("%d %d\n",&n,&m);int bb=0;ans=tot=q=0;
fo(i,1,n)
{
a[i][m+1]=0;
fo(j,1,m)
{
char ch;scanf("%c",&ch);a[i][j]=(ch=='.')?0:1;
if(ch=='X') q++;a[n+1][j]=0;
}
scanf("\n");
}
fo(i,1,n) fo(j,1,m)
{
int w=0;fo(k,0,8) if(a[i+o[k]][j+p[k]]==0) w++;
if(a[i][j]==1&&w!=8) bb=1;
if(w==9) d[++tot][0]=i,d[tot][1]=j;
}
if(q==0||bb==1) {printf("0\n");continue;}
dg(1,0);printf("%lld\n",ans);
}
}