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
X.
..
.X
Sample Output
60
HINT
Source
著名大佬：看到计数类问题就要想到容斥
数据范围十分小很容易想到状态压缩，而且我们发现，局部最小解最多只有8个。
我们可以用f[i][sta]表示填了1-i个数，已经填完了状态为sta的方案数，然后剩下的
随便去填，但是这样会有一个问题，就是在其它'.'的位置，如果填成了局部最小解怎么办。
这样就会有多的方案算进去。
所以就要用容斥的方法去解决这个问题。
那f[i][sta]怎么算。
格式写不出来。
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}