真的是神仙题，看了 PoPoQQQ 的题解才会做的
我们首先发现一个显然的性质，$4\times 7$的矩阵是只有可能有最多 8 个局部极小值的，否则随便鸽巢一下就能知道一定是不合法的状况。
我们考虑状压这 8 个位置是否填了数，我们发现你按表格顺序填是基本送命的，所以我们考虑从 $1$到 $mn$填数。
所以我们设 $f[i][s]$表示当前填到第 $i$个数状态为 $s$的时候的方案数。
我们会发现按顺序填会有很多好处，那么我们说说好处都有啥
首先对于一个未填的极小点，它的周围 8 个当前都不能填数，否则它就不是极小的了。
对于一个填了的极小点，你可以放心地在它周围填数，因为当前的点都是比它大的（废话）。
那么每次填数的时候，如果填到了极小点上，那么转移显然是
$$f[i][s]+=\sum_{x \in s}f[i-1][s-\{x\}]$$
那如果当前填到了非极小点上，那么我们怎么转移呢，初步 yy 一下大概是这样子的
$$f[i][s] += f[i-1][s] \times cnt$$
其中 $cnt$表示当前能放在的非极小点的位置数
那么每次我们都要预处理一遍 $cnt$吗
可以发现 $cnt$是可以根据状态 $s$预处理的，对于每个极小点，周围的点显然是不能填的，因为你没放在极小点上，所以极小点也是不能填的，那么一个状态 $s$的 $cnt$也就是整个棋盘减去上面说的那些点再减去已经填了的 $i-1$个点（注意，这 $i-1$个点与这上面说的不能填的点是没有交集的，这是这道题这样做的正确性的关键）
那么我们改一下方程，设 $cnt_s$表示 $s$状态能填多少点。方程改为
$$f[i][s]+=f[i-1][s]\times (cnt_s – i + 1)$$
但是这里还有一个细节，你现在保证了题目指定的极小点是极小点，但是你不能保证那些非极小点不是极小点，怎么办呢？你可以暴力 dfs 容斥它，把所有的棋盘情况 dfs 一遍，然后用原来的矩阵-多一个极小点的矩阵+多两个极小点的矩阵-…
代码:
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define mod 12345678
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 500005
#define ls (k << 1)
#define rs (k << 1 | 1)
const int tx[9] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
const int ty[9] = {0, -1, 0, 1, -1, 1, -1, 0, 1};
char ch[5][10];
int n, m, f[30][260], ans, map[5][10], up, cnt[260], up2;
int vis[5][10], tim;
inline void work ()
{
int tot = 0;
fo (i, 1, n)
fo (j, 1, m)
if (ch[i][j] == 'X')
map[i][j] = ++tot;
else
map[i][j] = 0;
up = (1 << tot) - 1;
fo (s, 0, up)
{
++tim;
cnt[s] = up2;
fo (i, 1, n)
fo (j, 1, m)
if (map[i][j] && !((1 << map[i][j] - 1) & s))
{
--cnt[s];//未被当前状态覆盖的低点不能放
fo (k, 1, 8)
{
int nx = i + tx[k], ny = j + ty[k];
if (!nx || !ny || n < nx || m < ny) continue;
if (vis[nx][ny] != tim)
{
vis[nx][ny] = tim;
--cnt[s];//在未覆盖低点旁边的点不能放
}
}
}
}
f[0][0] = 1;
fo (s, 0, up)
fo (i, 1, up2)
{
f[i][s] = 1ll * f[i - 1][s] * (cnt[s] - i + 1) % mod;
fo (k, 1, tot)
if (s & (1 << k - 1))
f[i][s] = (f[i][s] + f[i - 1][s ^ (1 << k - 1)]) % mod;
}
}
inline void dfs (int x, int y, int sum)
{
if (m < y)
{
dfs(x + 1, 1, sum);
return;
}
if (n < x)
{
work();
ans = (ans + (sum & 1 ? -1 : 1) * f[up2][up]) % mod;
return;
}
if (ch[x][y] != 'X')
{
fo (k, 1, 8)
{
int nx = x + tx[k], ny = y + ty[k];
if (!nx || !ny || n < nx || m < ny) continue;
if (ch[nx][ny] == 'X')
{
dfs(x, y + 1, sum);
return;
}
}
ch[x][y] = 'X';
dfs(x, y + 1, sum + 1);
ch[x][y] = '.';
}
dfs(x, y + 1, sum);
}
int main ()
{
scanf("%d %d", &n, &m); up2 = n * m;
fo (i, 1, n)
scanf("%s", ch[i] + 1);
fo (i, 1, n)
fo (j, 1, m)
if (ch[i][j] == 'X')
fo (k, 1, 8)
{
int nx = i + tx[k], ny = j + ty[k];
if (!nx || !ny || n < nx || m < ny) continue;
if (ch[nx][ny] == 'X')
{
printf("0\n");
return 0;
}
}
dfs(1, 1, 0);
printf("%d\n", (ans + mod) % mod);
return 0;
}
这道题蒟蒻 qhy 跑了两次 90 分，原因是矩阵大小只开了 $5\times 8$，虽然这里 m 是 7，并且我是从下标 1 开始存的，但是读入的时候字符串末尾会有个万恶的回车符，然后我的字符数组就乐滋滋地爆了。所以以后不要吝啬开这种数组否则死得早。
noip 成绩出来了，没机会去 pkuwc 了，自闭了，估计一段时间不会更 blog 了，作为弱校的杠把子估计还退不了役，不过我估计我这么菜离退役不远了。
0 条评论