【BZOJ 2669】 2669: [cqoi2012]局部极小值（状压DP+容斥原理）

2669: [cqoi2012]局部极小值

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 667 Solved: 350

Description

有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。

给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

Input

输入第一行包含两个整数n和m（1<=n<=4, 1<=m<=7），即行数和列数。以下n行每行m个字符，其中“X”表示局部极小值，“.”表示非局部极小值。

Output

输出仅一行，为可能的矩阵总数除以12345678的余数。

Sample Input

3 2
X.
..
.X

Sample Output

60

HINT

Source

【分析】

　　我好蠢啊。。。

　　保证每个数各不相同，又有大小关系，那么、、数字从小到大填。

　　其实局部极小值<=8的，这个可以状压，$f[i][j]$表示填了前i个数，局部极小值被填的状态是j的方案数。

　　有：

　　$f[i][j]=f[i-1][j]*(p[j]-i+1)+f[i-1][j-(1<<X)]$

　　但是，还要保证一点是非极小值一定非极小，上面没有保证，

　　所以枚举哪些非极小弄成了极小，容斥算出正确答案即可。

　　复杂度？$O（dfs*n*m*8*2^8）$大概是这样吧。。数据很小嘛。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Mod 12345678

 #define LL long long

 int a[][],num[][],p[];

 int n,m;

 int bx[]={,,,-,,,-,,-},

     by[]={,,,,-,,-,-,};

 char s[];

 bool vis[][];

 LL f[][],ans=;

 LL get_ans()

 {

     int cnt=;

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++) if(a[i][j]==) num[i][j]=++cnt;

     for(int k=;k<=(<<cnt)-;k++)

     {

         for(int i=;i<=n;i++) for(int j=;j<=m;j++) vis[i][j]=;

         for(int i=;i<=n;i++)

          for(int j=;j<=m;j++) if(a[i][j]==&&((<<num[i][j]-)&k)==)

          {

              for(int l=;l<=;l++)

              {

                 int nx=i+bx[l],ny=j+by[l];

                 vis[nx][ny]=;

              }

          }

         p[k]=;

         for(int i=;i<=n;i++)

          for(int j=;j<=m;j++) if(vis[i][j]&&a[i][j]==) {p[k]++;vis[i][j]=;}

         for(int i=;i<=cnt;i++) if((<<i-)&k) p[k]++;

     }

     memset(f,,sizeof(f));

     f[][]=;

     for(int i=;i<=n*m;i++)

      for(int j=;j<=(<<cnt)-;j++)

      {

          f[i][j]=f[i-][j]*(p[j]-i+);f[i][j]%=Mod;

          for(int k=;k<=cnt;k++) if((<<k-)&j)

          {

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

              f[i][j]%=Mod;

          }

      }

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

 }

 void dfs(int x,int y,int f)

 {

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

     if(x==n+)

     {

         ans+=f*get_ans();

         ans=(ans%Mod+Mod)%Mod;

         return;

     }

     if(a[x][y]==) {dfs(x,y+,f);return;}

     bool ok=;

     for(int i=;i<=;i++)

     {

         int nx=x+bx[i],ny=y+by[i];

         if(nx<||nx>n||ny<||ny>m) continue;

         if(a[nx][ny]==) {ok=;break;}

     }

     if(ok)

     {

         a[x][y]=;

         dfs(x,y+,-f);

         a[x][y]=;

     }

     dfs(x,y+,f);

 }

 int main()

 {

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

     for(int i=;i<=n;i++)

     {

         scanf("%s",s+);

         for(int j=;j<=m;j++)

         {

             if(s[j]=='X') a[i][j]=;

             else a[i][j]=;

         }

     }

     for(int i=;i<=n;i++)

      for(int j=;j<=m;j++) if(a[i][j]==)

      {

          for(int k=;k<=;k++)

          {

              int nx=i+bx[i],ny=j+by[i];

              if(nx<||nx>n||ny<||ny>m) continue;

              if(a[nx][ny]==) {printf("0\n");return ;}

          }

      }

     // memset(vis,1,sizeof(vis));

     dfs(,,);

     printf("%lld\n",ans);

     return ;

 }

2017-04-06 10:08:51

巴特西

【BZOJ 2669】 2669: [cqoi2012]局部极小值（状压DP+容斥原理）

2669: [cqoi2012]局部极小值

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

【BZOJ 2669】 2669: [cqoi2012]局部极小值 （状压DP+容斥原理）

2669: [cqoi2012]局部极小值

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

【BZOJ 2669】 2669: [cqoi2012]局部极小值（状压DP+容斥原理）