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）$大概是这样吧。。数据很小嘛。。。

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 #define Mod 12345678  8 #define LL long long  9  10 int a[5][8],num[5][8],p[310]; 11 int n,m; 12 int bx[10]={
    0,1,0,-1,0,1,-1,1,-1}, 13     by[10]={
    0,0,1,0,-1,1,-1,-1,1}; 14 char s[10]; 15 bool vis[5][8]; 16 LL f[30][310],ans=0; 17  18 LL get_ans() 19 { 20     int cnt=0; 21     for(int i=1;i<=n;i++) 22      for(int j=1;j<=m;j++) if(a[i][j]==1) num[i][j]=++cnt; 23     for(int k=0;k<=(1<
           
            n||ny<1||ny>m) continue; 70 if(a[nx][ny]==1) {ok=0;break;} 71 } 72 if(ok) 73 { 74 a[x][y]=1; 75 dfs(x,y+1,-f); 76 a[x][y]=0; 77 } 78 dfs(x,y+1,f); 79 } 80 81 int main() 82 { 83 scanf("%d%d",&n,&m); 84 for(int i=1;i<=n;i++) 85 { 86 scanf("%s",s+1); 87 for(int j=1;j<=m;j++) 88 { 89 if(s[j]=='X') a[i][j]=1; 90 else a[i][j]=0; 91 } 92 } 93 for(int i=1;i<=n;i++) 94 for(int j=1;j<=m;j++) if(a[i][j]==1) 95 { 96 for(int k=1;k<=8;k++) 97 { 98 int nx=i+bx[i],ny=j+by[i]; 99 if(nx<1||nx>n||ny<1||ny>m) continue;100 if(a[nx][ny]==1) {printf("0\n");return 0;}101 }102 }103 // memset(vis,1,sizeof(vis));104 dfs(1,1,1);105 printf("%lld\n",ans);106 return 0;107 }
           
          
         
        
       
      

 

2017-04-06 10:08:51