题解：P9263 [PA 2022] Bakterie

· · 题解

由于没有题解，并且官方题解是波兰语，这是官方题解的翻译。

尝试理解极限的意义。f(k) 是格子中细菌的期望值之和，将和拆开，算每个格子的细菌数。对于一个格子极限，表示该格子的存活率。所以将过程看作，每个 0 的格子保持为 0，而每个 1 的格子保持为 1，并将过程转化为连续的时间模型。即，若经过时间 \Delta t，每条边的端点都将减少 \Delta t。每个节点的值减少量是 \Delta t 乘以度数。

通过寻找规律，我们可以得出一些观察结果，它们也会在正解中被证明：

假设没有问号，将格子按照值是否会归零分为两类。我们需要计算格子在何时会归零。

假设我们能遍历所有有理数，对于在时间 t 归零的格子，它们有四个相邻点。这些相邻点中的每一个，要么严格早于时间 t 归零，要么至少在 t 时归零（不会归零的格子看作后者）。假设一个格子的两个相邻点，分别在 t_1 和 t_2（小于 t）时归零，而另外两个相邻点在 t 时归零（或者不归零）。那么满足：

t = \frac{1 - t_1 - t_2}{4 - 2}

类似地，如果有一个在 t_1 时刻归零，那么满足：

t = \frac{1 - t_1}{4 - 1}

对于 t，有四个分数，范围在 [0, t] 之间，表示相邻点的归零时间（t 表示稍后归零或不归零）。对于 t，这个四元组满足，1 减去小于 t 的分数的和，再除以等于 t 的分数的数量等于 t。此外，对于四元组中的每个小于 t 的分数，我们必须知道能产生这个分数的邻域状态。

最早能找到的分数是 t = \frac{1}{4}，表示一个格子为 1，四个相邻点也为 1。我们怎么求这个状态呢？对于 t = \frac{1}{4}，找到四元组：

\left( \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4} \right)

这表示每个相邻点最早在时刻 t 归零。等等，实际上我们还不知道 t > 0 时的任何状态，我们要计算这些！所以不能选择那些在时刻大于等于 \frac{1}{4} 的相邻点状态。我们怎么应对呢？既然我们知道所有在 t = \frac{1}{4} 之前归零的状态，那么那些在 t 或更晚时归零的状态就是……剩下的所有！事实上，零格子的对立面就是一格子。对于 t = \frac{1}{4}，状态是通过将一个空格放在中心，并在它四周放置空格的对立面来获得的。

反之，将更复杂的状态进行转换就更困难了。与其直接使用状态，不如为每个分数构建决策树，决策树可以用来判断某个格子的邻域是否属于某个状态集合。这样的决策树应该告诉我们在邻域内应该测试哪些格子，并且在每个分支处检查下一步。树的叶子部分会是“真”或“假”，即邻域是否符合某个状态（或更准确地说，是否符合某个状态集合）。

这些工具容易实现反转操作——只需在所有叶子节点中将“真”与“假”互换。那么到目前为止，我们的算法是怎么样的呢？我们遍历分数 t，寻找合适的四元组。如果四元组中包含某个小于 t 的分数，我们就尝试插入为此分数提前计算出的每个决策树。如果某个分数为 t，表示格子在 t 时刻最早归零，我们需要插入一个关于所有小于 t 分数的决策树反转状态。

这意味着还要实现两个决策树的或操作。我们复制第一个决策树，将其粘贴到第二个决策树中所有“假”分支的叶子节点中。但由于我们需要处理的分数和状态数量不小，决策树的大小依然可能爆炸。

尝试优化。如果我们沿着路径钦定了某个格子的状态，但之后我们又要对它测试，那就完全浪费了，因此可以优化掉整个子树。第二种优化是，如果整个子树是定值，那么我们将整个子树替换成一个叶子节点。

为了将四个决策树合并（以生成新的状态集合或决策树），我们还需要能够计算它们的和操作，但这与计算或操作是类似的。

我们可以将这个过程写成不假设任何分数的形式，最终得出所有遍历过的分数的分母将是 24 的因子。然而，也可以观察暴力解法，通过 assert 来验证。

现在对于每个合法的 t，已经有了判断某个格子是否会在 t 时归零的决策树。如果某个格子最终会有 b 个细菌，那么它的相邻点归零的时间总和必须为 1 - b（并且它们都必须归零）。

对于每个 b，我们都有一组决策树。不过现在，我们可以从这些决策树中生成一组状态。这些状态描述了格子的邻域，并告知某些位置必须是 1 或 0。如果某个格子的邻域符合某个 b 的状态，则表示最终该格子中会有 b 个细菌。

我们最终会得到多少个状态？这很难说，这取决于具体的实现，但可能会在 1500 到几万之间。这些状态有多大？实际上，邻域中重要的格子仅有 51 个，最大状态的大小为 30。那么这意味着什么呢？这是一个很好的时机来回顾一下，棋盘上仍然有问号字符。将状态应用到某个位置时，首先检查该位置是否与任何非问号的格子冲突；然后计算该状态内问号字符的数量。该状态匹配的概率为 (1/2)^{\text{问号字符数量}}。为了加速，我们使用位运算。

由于某个状态匹配某个位置的概率总是 (1/2)^k，其中 k 是一个整数，范围在 [0, 30] 内（前提是该概率不为零），我们可以推断出，我们输出的分数的分母总是 24 · 2^{30} 的因子。分子至多是棋盘大小 nm 的倍数，因此幸运的是，它仍然在 long long 范围内。

尽管有巨大的常数，复杂度仍为 O(nm)。