给定一个n∗m的矩阵，标记出其中的局部极小值，要求填入1…n∗m，求方案数 n*m≤25~30
BZOJ 2669 局部极小值(PoPoQQQ)
原来只考虑了保证标记的位置都是局部最小值
但是问题是这样虽然保证了标记的位置都是局部最小值，但是可能会导致一些未标记的位置成为局部极小值，因此我们枚举其他可以成为局部极小值的位置，容斥一下即可
所以正解是枚举每一种可能的局部最小值分布，用状压dp求出方案数，然后容斥（一步减，两步加）
对这种先搜索再dp的题的复杂度很不适应: O(Status∗29∗n∗m∗8) 祭奠先bfs后dp的Turn Game
#include <set> #include <ctime> #include <queue> #include <cstdio> #include <bitset> #include <cctype> #include <bitset> #include <cstdlib> #include <cassert> #include <cstring> #include <iostream> #include <algorithm> #define inf (1<<30) #define INF (1ll<<62) #define fi first #define se second #define rep(x,s,t) for(register int x=s,t_=t;x<t_;++x) #define per(x,s,t) for(register int x=t-1,s_=s;x>=s_;--x) #define travel(x) for(int I=last[x],to;~I&&(to=e[I].to,1);I=e[I].nxt) #define prt(x) cout<<#x<<":"<<x<<" " #define prtn(x) cout<<#x<<":"<<x<<endl #define pb(x) push_back(x) #define hash asfmaljkg #define rank asfjhgskjf #define y1 asggnja #define y2 slfvm using namespace std; typedef long long ll; typedef pair<int,int> ii; template<class T>void sc(T &x){ int f=1;char c;x=0; while(c=getchar(),c<48)if(c=='-')f=-1; do x=x*10+(c^48); while(c=getchar(),c>47); x*=f; } template<class T>void nt(T x){ if(!x)return; nt(x/10); putchar(x%10+'0'); } template<class T>void pt(T x){ if(x<0)putchar('-'),x=-x; if(!x)putchar('0'); else nt(x); } template<class T>void ptn(T x){ pt(x);putchar('\n'); } template<class T>void pts(T x){ pt(x);putchar(' '); } template<class T>inline void Max(T &x,T y){if(x<y)x=y;} template<class T>inline void Min(T &x,T y){if(x>y)x=y;} int n,m,nn; const int maxn=6; const int maxm=6; char ch[maxn][maxn]; const int rx[]={-1,-1,-1,0,0,1,1,1}; const int ry[]={-1,0,1,-1,1,-1,0,1}; const int mod=772002; const int maxx=9; ll rem[1<<maxx]; int ay[maxx]; int ax[maxx]; int tot; ll dp[maxn*maxn][1<<maxx];//roll? inline bool free(int x,int y){ rep(k,0,8){ int nx=x+rx[k],ny=y+ry[k]; if(nx<0||nx>=n||ny<0||ny>=m)continue; if(ch[nx][ny]=='X') return false; } return true; } int deal(){ tot=0; rep(i,0,n)rep(j,0,m)if(ch[i][j]=='X') ax[tot]=i,ay[tot++]=j; rep(mask,0,1<<tot){ rep(i,0,tot)if(mask>>i&1)ch[ax[i]][ay[i]]='.'; ll &cnt=rem[mask]=0; rep(i,0,n)rep(j,0,m) if(ch[i][j]=='.'&&free(i,j)) cnt++; rep(i,0,tot)if(mask>>i&1)ch[ax[i]][ay[i]]='X'; } dp[0][0]=1; rep(i,1,nn+1)rep(mask,0,1<<tot){ dp[i][mask]=dp[i-1][mask]*max(rem[mask]-i+1,0ll)%mod; for(int j=mask;j;j^=j&-j) (dp[i][mask]+=dp[i-1][mask^(j&-j)])%=mod; } return dp[nn][(1<<tot)-1]; } ll ans; void dfs(int x,int y,int cnt){ if(x==n){ // rep(i,0,n)prtn(ch[i]); (ans+=cnt&1?mod-deal():deal())%=mod; return; } int ny=y==m-1?0:y+1; int nx=y==m-1?x+1:x; dfs(nx,ny,cnt); if(ch[x][y]=='.'&&free(x,y)){ ch[x][y]='X'; dfs(nx,ny,cnt^1); ch[x][y]='.'; } } void solve(){ nn=n*m; tot=0; rep(i,0,n)scanf("%s",ch[i]); rep(i,0,n)rep(j,0,m) if(ch[i][j]=='X'&&!free(i,j)){ puts("0"); return; } ans=0; dfs(0,0,0); ptn(ans); } int main(){ // freopen("pro.in","r",stdin); // freopen("chk.out","w",stdout); int kase=0; while(~scanf("%d%d",&n,&m)){ printf("Case #%d: ",++kase); solve(); } return 0; }