BZOJ2669 [cqoi2012]局部极小值 状压DP 容斥原理

时间:2021-09-29 09:11:44

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ2669


题意概括

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

给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。
  几组例子:

1.in

1.out

1 3

.X.

2

2.in

2.out

2 2

X.

.X

0

3.in

3.out

3 2

X.

..

.X

60

4.in

4.out

3 6

....X.

......

.X...X

869490


题解

  大半个月没发博文了,冒个泡(也许我太弱了,又在放水题)

  这题有一个大大的坑点。

  要保证'.'不是局部极小值。

  我们先假设可以不保证这个东西。

  对于某一个局面(已知某些位置一定是局部最小值,其他位置不一定是局部最小值),我们如果要求得方案总数,可以写状压dp。

  我们把局部最小点的占用情况状态压缩一下。

  然后用dp[i][j]表示填了前i个数字(即1..i),然后局部最小点的占用状态为j的方案总数。

  那么自然,我们要预处理2个值。

  一个是当前状态下的局部最小点占用数cnt_chosen[i](当然这个不预处理也可以的……)

  一个是当前状态下多少非局部最小点是可以填数的,记为cnt_clock[i](博主英语不好,不要介意)

  在不断选择点的过程中,这个数是很有用的,而且不会受到后来填的数的影响。

  那么,对于dp[i][j],接下来可行的非局部最小点数就是relax_clock = cnt_clock[j] - (i - cnt_chosen[j])。

  具体那个cnt_clock怎么求,就是除掉局部最小点以及未选择的局部最小点周围的8连通点以外的点数。

  那么转移方程分成两个部分,一个是接下来选择一个非局部最小点,有relax_clock种方案。

  另一种是选择一个未选择的局部最小点,这个基本上是基础的状压dp。

  接下来是最强大的一步了!

  怎么避免原来的非局部最小点也变成局部最小点呢?

  答案是  ——  容斥!!!

  可怕,用dfs操作,奇加偶减即可。


代码

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
using namespace std;
const int N=10,M=15,P=10,S=1<<9,mod=12345678;
int n,m,s,totp,cnt_clock[S],cnt_chosen[S],dp[30][S],ans;
bool f[N][M];
struct Point{
int x,y;
Point (){}
Point (int x_,int y_){
x=x_,y=y_;
}
}p[P];
void init(){
char ch[N][M];
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%s",ch[i]+1);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j]=ch[i][j]=='.'?0:1;
}
bool check(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=m;
}
bool fail_simple_judge(){// judge of 0
FOR(i,1,n)
FOR(j,1,m)
if (f[i][j])
FOR(x,i-1,i+1)
FOR(y,j-1,j+1)
if ((x!=i||y!=j)&&check(i,j)&&f[x][y])
return 1;
return 0;
}
void getp(){
totp=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (f[i][j])
p[totp++]=Point(i,j);
}
void get_cnt(){
bool g[N][M],mark[N][M];
s=1<<totp;
for (int i=0;i<s;i++){
memset(g,0,sizeof g);
memset(mark,0,sizeof mark);
cnt_chosen[i]=cnt_clock[i]=0;
for (int j=0;j<totp;j++)
if (i&(1<<j))
cnt_chosen[i]++;
else {
Point v=p[j];
int x=v.x,y=v.y;
g[x][y]=1;
}
FOR(x,1,n)
FOR(y,1,m)
if (g[x][y])
FOR(a,x-1,x+1)
FOR(b,y-1,y+1)
if (check(a,b))
mark[a][b]=1;
for (int j=0;j<totp;j++){
Point v=p[j];
int x=v.x,y=v.y;
mark[x][y]=1;
}
FOR(x,1,n)
FOR(y,1,m)
if (!mark[x][y])
cnt_clock[i]++;
}
}
int DP(){
getp();
get_cnt();
memset(dp,0,sizeof dp);
dp[0][0]=1;
for (int i=0;i<n*m;i++)
for (int j=0;j<s;j++){
if (dp[i][j]==0)
continue;
int relax_clock=cnt_clock[j]-(i-cnt_chosen[j]);
dp[i+1][j]=(dp[i+1][j]+1LL*dp[i][j]*relax_clock%mod)%mod;
for (int k=0;k<totp;k++)
if (!(j&(1<<k))){
int j_=j|(1<<k);
dp[i+1][j_]=(dp[i+1][j_]+dp[i][j])%mod;
}
}
return dp[n*m][s-1];
}
void dfs(int x,int y,int op,int add){
if (add)
ans=(ans+DP()*op+mod)%mod;
int x_=x,y_=y;
if (x==n&&y==m)
return;
if (y==m)
x_++,y_=1;
else
y_++;
dfs(x_,y_,op,0);
FOR(i,x-1,x+1)
FOR(j,y-1,y+1)
if (check(i,j)&&f[i][j])
return;
f[x][y]=1;
dfs(x_,y_,-op,1);
f[x][y]=0;
}
int main(){
init();
if (fail_simple_judge()){
printf("0");
fclose(stdin);fclose(stdout);
return 0;
}
ans=0;
dfs(1,1,1,1);
printf("%d",ans);
return 0;
}