[BZOJ2669][CQOI2012]局部最小值(容斥+状压DP)

发现最多有8个限制位置，可以以此为基础DP和容斥。

$f_{i,j}=f_{i-1,j}\times (cnt_j-i+1)+\sum_{k\subset j} f_{i-1,k}$

$cnt_j$表示当限制状态为j时i有多少个可行位置。

这样DP只能保证所有题设位置全部是局部最小值，但不保证其它位置不会变成局部最小值，容斥解决。

$O(DFS*8nm*2^8)$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int mod=;

 int dx[]={,,,-,,,-,,-},dy[]={,,,,-,,-,-,};

 int n,m,ans,l,f[][<<],cnt[<<],vis[][],a[][];

 char ch[][];

 int dp(){

     memset(f,,sizeof(f));

     memset(cnt,,sizeof(cnt));

     int top=;

     rep(i,,n) rep(j,,m) if (ch[i][j]=='X')

         a[++top][]=i,a[top][]=j;

     for (int S=; S<(<<top); S++){

         memset(vis,,sizeof(vis));

         rep(i,,top) if (~S&(<<(i-))) vis[a[i][]][a[i][]]=;

         rep(i,,n) rep(j,,m){

             bool flag=;

             rep(l,,) if (vis[i+dx[l]][j+dy[l]]) { flag=; break; }

             if (!flag) cnt[S]++;

         }

     }

     f[][]=;

     rep(i,,n*m) for (int j=; j<(<<top); j++){

         f[i][j]=(f[i][j]+1ll*f[i-][j]*max(cnt[j]-i+,))%mod;

         rep(k,,top) if (j&(<<(k-)))

             f[i][j]=(f[i][j]+f[i-][j^(<<(k-))])%mod;

     }

     return f[n*m][(<<top)-];

 }

 void dfs(int x,int y,int t){

     if (y==m+){ dfs(x+,,t); return; }

     if (x==n+){ ans=(ans+dp()*(t&?-:))%mod; return; }

     dfs(x,y+,t);

     bool flag=;

     rep(i,,) if (ch[x+dx[i]][y+dy[i]]=='X') { flag=; break; }

     if (!flag) ch[x][y]='X',dfs(x,y+,t+),ch[x][y]='.';

 }

 int main(){

     freopen("bzoj2669.in","r",stdin);

     freopen("bzoj2669.out","w",stdout);

     scanf("%d%d",&n,&m);

     rep(i,,n) scanf("%s",ch[i]+);

     rep(i,,n) rep(j,,m) if (ch[i][j]=='X')

         rep(k,,) if (ch[i+dx[k]][j+dy[k]]=='X') { puts(""); return ; }

     dfs(,,); printf("%d\n",(ans+mod)%mod);

     return ;

 }