【CQOI 2012】【BZOJ 2669】【JZOJ 4700】 Garden

Description

Analysis

自此题本人在BZOJ上神一般的100%正确率没了！！ 好吧，扯远了。 首先，请读者再读一遍题，尤其要注意加粗的字，我就被坑了。 N≤4,M≤7？！ ，画一画，X的数量最多为8个。 那，我们从小到大填数，再状压一下X被填的状态。 那就有 f[i][s]=(∑i∈sf[i−1][s−i])+f[i−1][s]∗当前状态可以填的位置数 这些都很SIMPLE啦。 但是，请注意题目中的“只有”，这表示对于非X的位置，其周围的八个位置全部大于其亦是不合法的，但是我们的算法没有考虑到。 那就容斥咯。强制将那些位置变成X再做DP，容斥。

Code

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N=8,mo=12345678, fx[][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}}; int n,m,num,b0,ans,f[30][1<<N],rest[1<<N]; bool map[N][N],bz[N][N]; struct node { int x,y; }a[N],b[N]; bool pd() { fo(x,1,n) fo(y,1,m) if(map[x][y]) fo(k,0,7) { int xx=x+fx[k][0],yy=y+fx[k][1]; if(xx<1 || xx>n || yy<1 || yy>m) continue; if(map[xx][yy]) return 1; } return 0; } int dp() { num=0; fo(i,1,n) fo(j,1,m) if(map[i][j]) a[++num].x=i,a[num].y=j; memset(rest,0,sizeof(rest)); fo(s,0,(1<<num)-1) { memset(bz,1,sizeof(bz)); fo(i,1,num) if(!(s&(1<<(i-1)))) { int x=a[i].x,y=a[i].y; bz[x][y]=0; fo(k,0,7) { int xx=x+fx[k][0],yy=y+fx[k][1]; if(xx<1 || xx>n || yy<1 || yy>m) continue; bz[xx][yy]=0; } } fo(i,1,n) fo(j,1,m) if(bz[i][j]) rest[s]++; } memset(f,0,sizeof(f)); f[0][0]=1; fo(i,1,n*m) fo(s,0,(1<<num)-1) { f[i][s]=f[i-1][s]*(rest[s]-i+1)%mo; fo(k,1,num) if(s&(1<<(k-1))) f[i][s]=(f[i][s]+f[i-1][s^(1<<(k-1))])%mo; } return f[n*m][(1<<num)-1]; } void dfs(int cnt,int z) { if(cnt&1) ans=(ans-dp()+mo)%mo; else ans=(ans+dp())%mo; fo(i,z+1,b0) { int x=b[i].x,y=b[i].y; bool p=1; fo(k,0,7) { int xx=x+fx[k][0],yy=y+fx[k][1]; if(xx<1 || xx>n || yy<1 || yy>m) continue; if(map[xx][yy]){p=0;break;} } if(!p) continue; map[x][y]=1; dfs(cnt+1,i); map[x][y]=0; } } int main() { int _; char ch; for(scanf("%d",&_);_--;) { scanf("%d %d\n",&n,&m); fo(i,1,n) { fo(j,1,m) scanf("%c",&ch),map[i][j]=ch=='X'; scanf("\n"); } if(pd()) { printf("0\n"); continue; } b0=0; fo(x,1,n) fo(y,1,m) if(!map[x][y]) { bool p=1; fo(k,0,7) { int xx=x+fx[k][0],yy=y+fx[k][1]; if(xx<1 || xx>n || yy<1 || yy>m) continue; if(map[xx][yy]) {p=0;break;} } if(p) b[++b0].x=x,b[b0].y=y; } ans=0; dfs(0,0); printf("%d\n",ans); } return 0; }