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

2669: [cqoi2012]局部极小值

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

Description

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

Input

输入第一行包含两个整数nm(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][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}

上一篇:源码解读·RT-Thread小内存管理算法分析


下一篇:solr研磨之游标分页