bzoj 2669 [cqoi2012]局部极小值 DP+容斥

2669: [cqoi2012]局部极小值

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 838 Solved: 444
[Submit][Status][Discuss]

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

HINT

Source

著名大佬：看到计数类问题就要想到容斥

数据范围十分小很容易想到状态压缩，而且我们发现，局部最小解最多只有8个。

我们可以用f[i][sta]表示填了1-i个数，已经填完了状态为sta的方案数，然后剩下的

随便去填，但是这样会有一个问题，就是在其它'.'的位置，如果填成了局部最小解怎么办。

这样就会有多的方案算进去。

所以就要用容斥的方法去解决这个问题。

那f[i][sta]怎么算。
bzoj 2669 [cqoi2012]局部极小值 DP+容斥

格式写不出来。

cnt的话就是暴力2*8*n*m*9 一次60000的复杂度而已，9代表判断周围。

f[i][j]=f[i-1][j](前面填了1-i中就已经填好了j这个状态，那么剩下就在cntj-(i-1))选一个，（因为cnt包含了

局部最小解个数），加上，所有的当前，填这一个最小解的方案数。因为填的数是不同的，所以是不同

状态。

复杂度是 2*8 *2*8*n*m*9差不多10000000这是极限

 #pragma GCC optimize(2)

 #pragma G++ optimize(2)

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #define MOD 12345678

 using namespace std;

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

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

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,ans;

 char s[][];

 int Calculate()

 {

     static pair<int,int> stack[];

     static int cnt[<<],f[][<<];

     int i,j,k,sta,top=;

     memset(cnt,,sizeof cnt);

     memset(f,,sizeof f);

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

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

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

                 stack[++top]=pair<int,int>(i,j);

     for(sta=;sta<<<top;sta++)

     {

         static bool unfilled[][];

         memset(unfilled,,sizeof unfilled);

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

             if(~sta&(<<i-))

                 unfilled[stack[i].first][stack[i].second]=true;

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

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

             {

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

                     if(unfilled[i+dx[k]][j+dy[k]])

                         break;

                 if(k==)

                     cnt[sta]++;

             }

     }

     f[][]=;

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

             for(sta=;sta<<<top;sta++)

             {

                 (f[i][sta]+=(long long)f[i-][sta]*max(cnt[sta]-i+,))%=MOD;

                 for(j=;j<=top;j++)

                     if(sta&(<<j-))

                         (f[i][sta]+=f[i-][sta^(<<j-)])%=MOD;

             }

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

 }

 void DFS(int x,int y,int cnt)

 {

     int i;

     if(y==m+)

     {

         DFS(x+,,cnt);

         return ;

     }

     if(x==n+)

     {

         (ans+=Calculate()*cnt)%=MOD;

         return ;

     }

     DFS(x,y+,cnt);

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

         if(s[x+dx[i]][y+dy[i]]=='X')

             break;

     if(i==)

     {

         s[x][y]='X';

         DFS(x,y+,-cnt);

         s[x][y]='.';

     }

 }

 int main()

 {

     int i,j,k;

     n=read(),m=read();

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

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

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

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

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

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

                     if(s[i+dx[k]][j+dy[k]]=='X')

                         return puts(""),;

     DFS(,,);

     cout<<(ans+MOD)%MOD<<endl;

 }

fi,j=fi−1,j∗C1cntj−i+1+∑k∈jfi−1,j−{k}

秒客网