CQOI2012局部极小值

P3160 CQOI2012局部极小值

一个 $n\times m$ 的矩阵填满 $1-n\times m$ 的数，称一个格子为关键点当且仅当其周围的格子都比他大。

现给您矩阵中关键点的位置，求出可能的矩阵个数（$n\le 4,m\le 7$）。

考虑状压。

考虑关键点的形成方式，将 $1-n\times m$ 的数依次加入矩阵中，若当前加入的格子周围没有已加入的点，则他是关键点。

注意到其实关键点的个数最多只有 $8$ 个，则可以状压关键点的状态。但是我们不必存已经加入矩阵的点的信息来判断加入点是否是关键点，只需要在加入的时候把没有点的关键点的周围点排除即可。

令 $f_{i,S}$ 表示前 $i$ 个数，关键点的情况是 $S$ 的方案数，有一下转移：

$f_{i,S}=(\sum_{j\in S}f_{i-1,S\oplus j})+f_{i-1,S}\times (n-num_S-i+1)$

其中 $num_S$ 代表 $|T\oplus S|$ 再减去他们周围的点，即不能选的点个数。

但是这样直接算会将一些不是关键点的点变成关键点，考虑容斥，将所有可能的关键点集合搜出来，再算一遍那些包含题目中的集合的集合的 $\texttt {dp}$ 值，减去或加上即可。