自动搬运

查看原文

来自洛谷，原作者为

	drmr **

搬运于2025-08-24 22:46:52，当前版本为作者最后更新于2025-04-14 15:57:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

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

• 如果没有问号，那么细菌的期望总是分母为 $24$ 的分数。
• 细菌的数量仅与该格子的“邻域”有关。其中邻域指的是相邻点集合。

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

假设我们能遍历所有有理数，对于在时间 $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)$。