CoinsGame

作者：高杰

关键词：组合数学 计数 迭代 搜索

题目简述

一个$n \times m$的矩形棋盘，有一些格子被ban掉了，其余的每个格子你可以指定放或不放硬币。

放完硬币后你可以做若干次操作，每次操作你可以指定一个方向（上下左右），使所有的硬币尝试向那个方向移动一格。如果一个硬币的目标格子被ban那么它不会移动。硬币可以被移出棋盘（然后就掉在外面回不来了）。一个格子上可以有多枚硬币。

求有多少种放硬币的方案，满足存在一种操作序列使至少有一枚硬币被移出棋盘、同时至少有一枚硬币留在棋盘上。

数据范围

$1 \le n, m \le 40$

算法一

首先我们做几个约定：

• 一枚硬币的状态表示它是在棋盘上还是在棋盘外。

• 两枚硬币k-相同表示对于任意长度不大于$k$的操作序列，这两枚硬币的状态都相同。

• 两枚硬币本质相同表示对于任意的操作序列，这两枚硬币的状态都相同。

• 类似地可以定义k-不同和本质不同。

• 注意一枚硬币可以用它的位置唯一表示，下面不对“硬币”和“位置”做严格区分。

注意到需要满足的条件等价于存在两个被放置的硬币本质不同。因此我们的关键问题是如何求出哪些硬币是本质相同的。

下面给出一个解决该问题的算法：

1. 给每个位置贴一个label。初始时，所有棋盘内的位置label为1，棋盘外的位置label为0。

2. 对于每个棋盘内没有被ban的位置，计算这个硬币在一次操作（上下左右）后4个可能的位置，把这些位置的label取出来压成一个四元组。

3. 将这些四元组按照第一次出现的位置排序离散化，用离散化后的值作为每个位置新的label。

4. 如果所有的label都没有改变，那么算法结束；否则回到2继续迭代。

上述算法的第$i$次迭代后，两个位置i-相同当且仅当其label相同；算法结束时，两个位置本质相同当且仅当其label相同。下面用循环不变式证明这一点。

初始化：迭代开始时，棋盘内所有硬币的label都是1，显然它们都是0-相同的。

保持：在第$i$次迭代后，两个位置的label相同等价于任意做一次操作后，这两枚硬币新的位置在第$i$次迭代前的label相同（即(i-1)-相同），等价于这两个位置i-相同。

终止：算法终止意味着在连续两次迭代中得到了相同的结果。由于每次迭代得到的label都只与上一次迭代得到的label有关，因此若迭代继续下去，则每次得到的label都与这次相同。因此对于label相同的位置，对任意大的$k$，都有它们$k$相同，即它们本质相同。

以上并没有证明这个算法能够结束，在这里补上。对于两个位置$a, b$，设$i_1<i_2$，则$a$和$b$$i_1$-不同而$i_2$-相同的情况是不可能出现的，因此每次迭代都会使相互不同的位置的种类数增加，最多增加到$O(n\times m)$一定会结束。

实现了上述算法后剩下一些简单的统计工作。设若干组本质相同的位置个数分别是$cnt_1,cnt_2,\dots ,cnt_k$。一个方案不合法当且仅当只取了同一组里的位置，注意空集的情况，因此答案为$2^{\sum cnt_i}-1-\sum 2^{cnt_i}-1$。