Checkers - 题解

标签与难度

标签: 组合数学, 图论, 期望, 线性期望, 奇偶性分析, 思维题难度: 2100

题目大意喵~

好久不见呀，指挥官！今天我们来玩一个有趣的跳棋游戏，喵~

在一个二维坐标平面上，有 $N$ 个黑色的棋子，第 $i$ 个在 $(X_i, Y_i)$ 。游戏开始前，每个黑棋子都有 $1/2$ 的概率会消失。

我们的“一步棋”是这样定义的：

首先，在一个横坐标为偶数的位置 $(2x, y)$ （ $x, y$ 是整数）放一个白棋子 $W$ 。
只要 $W$ 的旁边（曼哈顿距离为1）有黑棋子 $B$ ，你就可以选择让 $W$ 跳过 $B$ 来吃掉它。 $W$ 会移动到它当前位置关于 $B$ 的对称点，然后 $B$ 就被移除了。这个吃子过程可以连续进行。
当 $W$ 旁边没有黑棋子可吃，或者你选择停下来时，这一“步”就结束了，白棋子 $W$ 会被拿走。

我们的目标是用最少的“步数”吃掉所有剩下的黑棋子。

问题是：在所有 $2^N$ 种黑棋子初始状态等概率出现的情况下，完成游戏所需的最少步数的期望是多少？题目告诉我们，如果期望是 $E$ ，那么 $E \cdot 2^N$ 一定是个整数。我们需要输出 $E \cdot 2^N$ 对 $1000000007$ 取模的结果。

解题思路分析

这道题看起来有点复杂，又是期望又是跳棋的，但别怕，让我带你一步步解开它的秘密，喵~

期望的转化

首先，我们来处理这个“期望”。题目要求的是期望步数 $E$ 。根据期望的定义， $E = \sum_{S} P(S) \cdot \text{MinMoves}(S)$ ，其中 $S$ 是所有 $2^N$ 种可能的黑棋子子集之一， $P(S)$ 是出现该子集的概率， $\text{MinMoves}(S)$ 是清理掉子集 $S$ 所需的最少步数。

因为每个棋子留下或消失的概率都是 $1/2$ ，所以任何一个特定的子集 $S$ （大小为 $k$ ）出现的概率是 $(1/2)^k \cdot (1/2)^{N-k} = (1/2)^N$ 。概率是均等的！

所以， $E = \sum_{S} \frac{1}{2^N} \cdot \text{MinMoves}(S)$ 。题目要求我们计算 $E \cdot 2^N$ ，那正好就是：

E \cdot 2^N = \sum_{S \subseteq \text{All Checkers}} \text{MinMoves}(S)

也就是说，我们只需要计算出对于所有 $2^N$ 种情况，每种情况的最少步数之和就可以啦！

白棋子的神秘舞步

接下来，我们来分析白棋子 $W$ 的移动规则。这是解题的关键哦！一个白棋子 $W$ 在 $(w_x, w_y)$ ，它跳过黑棋子 $B$ 在 $(b_x, b_y)$ ，会到达新位置 $(w_x', w_y')$ 。新位置是对称点，所以 $B$ 是 $W$ 和 $W'$ 的中点，即 $(b_x, b_y) = (\frac{w_x+w_x'}{2}, \frac{w_y+w_y'}{2})$ 。由此可得，新位置是 $W' = (2b_x - w_x, 2b_y - w_y)$ 。

我们来观察一下坐标的奇偶性，会发现两个非常重要的不变量：

横坐标的奇偶性：白棋子 $W$ 的起始位置是 $(2x, y)$ ，所以它的横坐标 $w_x$ 永远是偶数。当它跳过一个黑棋子 $B(b_x, b_y)$ 时，我们看看新位置的横坐标 $w_x' = 2b_x - w_x$ 。因为 $2b_x$ 是偶数， $w_x$ 也是偶数，所以 $w_x'$ 必然也是偶数！喵~ 这意味着白棋子的横坐标永远是偶数。
坐标和的奇偶性：白棋子 $W$ 的坐标和是 $w_x + w_y$ 。我们看看新位置的坐标和 $w_x' + w_y'$ 。 $w_x' + w_y' = (2b_x - w_x) + (2b_y - w_y) = 2(b_x+b_y) - (w_x+w_y)$ 。对2取模，我们得到 $(w_x' + w_y') \pmod 2 = -(w_x+w_y) \pmod 2 = (w_x+w_y) \pmod 2$ 。也就是说，一次跳跃并不改变白棋子坐标和的奇偶性！

棋盘的两个独立世界

这两个不变量告诉我们一个惊人的事实：棋盘被分成了两个完全独立的世界！

一个黑棋子 $B(b_x, b_y)$ 要被吃掉，白棋子 $W(w_x, w_y)$ 必须在它的邻居位置，即 $|w_x - b_x| + |w_y - b_y| = 1$ 。这说明 $(w_x+w_y)$ 和 $(b_x+b_y)$ 的奇偶性必然相反。

结合不变量，我们可以得出：

世界A：如果一个白棋子 $W$ 的起始坐标和 $(2x+y)$ 是偶数，那么在它的整个移动过程中，它的坐标和永远是偶数。它只能与坐标和为奇数的黑棋子互动。
世界B：如果一个白棋子 $W$ 的起始坐标和 $(2x+y)$ 是奇数，那么它的坐标和永远是奇数。它只能与坐标和为偶数的黑棋子互动。

这两个世界互不干扰！我们可以把所有的黑棋子分成两组：

$S_{odd} = \{i \mid (X_i+Y_i) \text{ 是奇数}\}$
$S_{even} = \{i \mid (X_i+Y_i) \text{ 是偶数}\}$

清理 $S_{odd}$ 的步数和清理 $S_{even}$ 的步数是完全独立的。因此，总步数和可以分解为：

\text{TotalSum} = (\sum_{C \subseteq S_{odd}} \text{MinMoves}(C)) \cdot 2^{|S_{even}|} + (\sum_{C \subseteq S_{even}} \text{MinMoves}(C)) \cdot 2^{|S_{odd}|}

现在，问题简化为分别计算两个组内的总步数和。我们以 $S_{even}$ 组为例来分析。

连线成片，化繁为简

对于 $S_{even}$ 组的黑棋子，白棋子 $W(w_x, w_y)$ 必须满足 $w_x$ 是偶数，且 $w_x+w_y$ 是奇数。

一个黑棋子 $B(b_x, b_y)$ 只有在它的邻居是合法的 $W$ 位置时，才能被连接成一条吃子路径。

如果 $B$ 的坐标是 (偶, 偶)，那么 $b_x+b_y$ 是偶数。它的邻居中， $(b_x, b_y \pm 1)$ 的横坐标是偶数，坐标和是奇数，是合法的 $W$ 位置。所以 (偶, 偶) 型的棋子只能形成竖直方向的连接。
如果 $B$ 的坐标是 (奇, 奇)，那么 $b_x+b_y$ 是偶数。它的邻居中， $(b_x \pm 1, b_y)$ 的横坐标是偶数，坐标和是奇数，是合法的 $W$ 位置。所以 (奇, 奇) 型的棋子只能形成水平方向的连接。

看呐！我们把问题转化成了一个图论模型。每个黑棋子是一个顶点。如果两个黑棋子可以被一个白棋子连续吃掉，就在它们之间连一条边。这个图的结构非常简单：它是一堆互不相交的、只由水平或竖直边构成的路径。这样的图我们称之为森林（没有环）。

一次“移动”（即放置一个白棋子开始一串连锁反应）可以清理掉一个连通块。所以，对于一个给定的棋子配置 $C$ ，最少移动步数 $\text{MinMoves}(C)$ 就等于这个配置下形成的图的连通块数量。

对于森林来说，有一个很棒的性质：连通块数量 = 顶点数 - 边数。所以， $\text{MinMoves}(C) = |C| - \text{Edges}(C)$ 。

最终的计算

现在我们来计算 $\sum_{C \subseteq S_{group}} \text{MinMoves}(C)$ ，其中 $S_{group}$ 是我们正在分析的一个组（比如 $S_{even}$ ）。

\sum_{C \subseteq S_{group}} \text{MinMoves}(C) = \sum_{C \subseteq S_{group}} (|C| - \text{Edges}(C))

利用和的线性性质，可以拆开：

= (\sum_{C \subseteq S_{group}} |C|) - (\sum_{C \subseteq S_{group}} \text{Edges}(C))

计算 $\sum |C|$ : 对于 $S_{group}$ 中的每一个棋子，它会出现在多少个子集 $C$ 中？答案是 $2^{|S_{group}|-1}$ 个（因为它自己必须在，其它棋子随意）。所以，这部分的和是 $|S_{group}| \cdot 2^{|S_{group}|-1}$ 。
计算 $\sum \text{Edges}(C)$ : 我们先找出所有可能形成的“边”，也就是所有相邻的黑棋子对。对于 $S_{even}$ 组，就是形如 ((x,y), (x,y+2)) 的 (偶,偶) 对，和 ((x,y), (x+2,y)) 的 (奇,奇) 对。设这样的对一共有 $k_{group}$ 个。对于每一个这样的对（一条潜在的边），它会出现在多少个子集 $C$ 中？只有当这对棋子同时存在于 $C$ 中时，这条边才算形成。这样的子集有 $2^{|S_{group}|-2}$ 个。所以，这部分的和是 $k_{group} \cdot 2^{|S_{group}|-2}$ 。

把它们合起来，一个组的总和就是：

\text{Sum}_{group} = |S_{group}| \cdot 2^{|S_{group}|-1} - k_{group} \cdot 2^{|S_{group}|-2}

这个公式可以应用到 $S_{odd}$ 和 $S_{even}$ 两组上。设 $N_{odd}=|S_{odd}|, N_{even}=|S_{even}|, N=N_{odd}+N_{even}$ 。设 $k_{odd}, k_{even}$ 分别是两组内的相邻棋子对数量， $k = k_{odd}+k_{even}$ 。

最终的总和是：

\begin{aligned} \text{TotalSum} &= \text{Sum}_{odd} \cdot 2^{N_{even}} + \text{Sum}_{even} \cdot 2^{N_{odd}} \\ &= (N_{odd} \cdot 2^{N_{odd}-1} - k_{odd} \cdot 2^{N_{odd}-2}) \cdot 2^{N_{even}} + (N_{even} \cdot 2^{N_{even}-1} - k_{even} \cdot 2^{N_{even}-2}) \cdot 2^{N_{odd}} \\ &= (N_{odd} \cdot 2^{N-1} - k_{odd} \cdot 2^{N-2}) + (N_{even} \cdot 2^{N-1} - k_{even} \cdot 2^{N-2}) \\ &= (N_{odd} + N_{even}) \cdot 2^{N-1} - (k_{odd} + k_{even}) \cdot 2^{N-2} \\ &= N \cdot 2^{N-1} - k \cdot 2^{N-2} \end{aligned}

这个公式可以进一步化简为 $(2N - k) \cdot 2^{N-2}$ 。这就是我们要的答案啦！

代码实现

现在，让我们把这个思路变成可爱的代码吧，喵~

cpp

#include <iostream>
#include <vector>
#include <set>
#include <utility>

// 使用 long long 防止计算过程中溢出
using ll = long long;

// 模块化的快速幂，用来计算 2 的幂次
ll power(ll base, ll exp) {
    ll res = 1;
    ll mod = 1000000007;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    // 使用 std::ios_base::sync_with_stdio(false) 和 std::cin.tie(NULL) 加速输入输出，是个好习惯喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 使用 std::set 来存储棋子坐标，可以快速查找，O(logN) 的效率很不错
    std::set<std::pair<int, int>> checkers;
    std::vector<std::pair<int, int>> checker_list(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> checker_list[i].first >> checker_list[i].second;
        checkers.insert(checker_list[i]);
    }

    ll k = 0; // k 用来统计所有相邻的棋子对数量

    // 遍历所有棋子，检查它们是否有“前辈”棋子
    for (int i = 0; i < n; ++i) {
        int x = checker_list[i].first;
        int y = checker_list[i].second;

        // 一个棋子 (x, y) 的潜在连接前辈只有两种：(x-2, y) 或 (x, y-2)
        // 我们不需要判断棋子属于哪个组，因为我的最终公式把所有情况都优雅地合并了喵~
        
        // 检查水平方向的前辈 (x-2, y) 是否存在
        if (checkers.count({x - 2, y})) {
            k++;
        }
        
        // 检查竖直方向的前辈 (x, y-2) 是否存在
        if (checkers.count({x, y - 2})) {
            k++;
        }
    }

    ll mod = 1000000007;

    // 计算 N * 2^(N-1)
    ll term1 = (ll)n * power(2, n - 1) % mod;
    
    // 计算 k * 2^(N-2)
    ll term2 = k * power(2, n - 2) % mod;

    // 最终结果是 (term1 - term2)
    ll ans = (term1 - term2 + mod) % mod;

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 。我们将 $N$ 个棋子坐标插入 std::set 中，每次插入需要 $O(\log N)$ 。之后遍历 $N$ 个棋子，每次在 std::set 中查找，也需要 $O(\log N)$ 。所以总的时间复杂度是 $O(N \log N)$ 。如果使用 std::unordered_set，平均时间复杂度可以达到 $O(N)$ 呢！
空间复杂度: $O(N)$ 。我们用了一个 std::set 和一个 std::vector 来存储 $N$ 个棋子的坐标，所以空间是线性的，喵~

知识点总结

这道题真是一次奇妙的思维探险！我们用到的知识点有：

期望的线性性质: 这是解决期望问题的基石。它让我们能把复杂问题的期望分解成简单问题的期望之和，或者像本题一样，将期望的计算转化为对所有情况求和。
不变量分析: 通过观察棋子跳跃规则，我们发现了白棋子横坐标和坐标和的奇偶性这两个不变量。这是打开局面的钥匙！
问题分解: 基于不变量，我们将问题分解为两个完全独立的子问题。这是算法设计中一个非常强大的思想，化整为零，各个击破！
图论建模: 我们把棋子和它们之间的连接关系看作图的顶点和边，将几何问题转化为图论问题。
组合计数: 最终的计算依赖于简单的组合计数思想，比如计算一个元素/一对元素会出现在多少个子集中。

通过这一系列的推理，我们把一个看起来需要复杂动态规划的问题，变成了一个简单的计数问题。是不是很有趣呀？希望指挥官能从中学到东西，下次遇到难题也能像我一样，找到那条最优雅的解题路径，喵~！

Checkers - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

期望的转化 ​

白棋子的神秘舞步 ​

棋盘的两个独立世界 ​

连线成片，化繁为简 ​

最终的计算 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​