「PA 2022」Wieczór gier 题解

题目大意

有一个 $n \times m$ 的棋盘，上面有 $k$ 个不可区分的棋子（$1 \le k \le nm-1$）。每一步操作是随机选择一个棋子，将其移动到相邻的空格中。问在经过 $100^{100^{100^{100}}}$ 步后，棋盘上的棋子排布与目标排布相同的概率。

解题思路

关键观察

1. 马尔可夫链的平稳分布：经过极其大量的步数后，系统会达到平稳分布
2. 二分图性质：棋盘可以看作二分图，根据 $(i+j)$ 的奇偶性染色
3. 奇偶性守恒：在移动过程中，棋子所在格子的颜色奇偶性总和保持不变

算法步骤

1. 奇偶性检查

   • 计算初始状态和目标状态中所有棋子所在位置的 $(i+j) \bmod 2$ 的异或和
   • 如果两者不等，概率为 $0$（因为无法通过合法移动达到目标状态）

2. 计算目标状态的可移动边数

   • 对于目标状态中的每个棋子，统计其可以移动到的相邻空位数量
   • 这个数量记为 dufin

3. 计算状态空间大小

   • 将棋盘分为奇数格和偶数格
   • 使用组合数计算所有可能的合法状态数量 dusum

4. 计算概率

   • 最终概率 = dufin / dusum / 总边数
   • 总边数为 $n(m-1) + m(n-1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

int n, m, sum;
char s[15][15], t[15][15];
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};

// 组合数计算
inline int C(int x, int y) {
    if (x < y || y < 0) return 0;
    int Ans = 1;
    for (int i = x - y + 1; i <= x; i++) Ans *= i;
    for (int i = 1; i <= y; i++) Ans /= i;
    return Ans;
}

int main() {
    cin >> n >> m;
    
    // 读入初始状态和目标状态
    for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
    for (int i = 1; i <= n; i++) cin >> (t[i] + 1);
    
    // 检查奇偶性是否匹配
    int fls = 0, flt = 0;
    sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'O') fls ^= ((i + j) & 1);
            if (t[i][j] == 'O') flt ^= ((i + j) & 1), sum++;
        }
    }
    
    if (fls != flt) {
        cout << "0.000000000000000000" << endl;
        return 0;
    }
    
    // 计算目标状态的可移动边数
    int dufin = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (t[i][j] == 'O') {
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 1 && y >= 1 && x <= n && y <= m && t[x][y] == '.')
                        dufin++;
                }
            }
        }
    }
    
    // 计算状态空间大小
    int odd = (n + 1) / 2 * (m / 2) + (m + 1) / 2 * (n / 2);
    int even = n * m - odd;
    int dusum = 0;
    
    for (int p = 0; p <= sum; p++)
        dusum += C(odd - 1, p) * C(even - 1, sum - 1 - p);
    
    // 计算最终概率
    double result = 1.0 * dufin / dusum / (n * (m - 1) + m * (n - 1));
    cout << fixed << setprecision(18) << result << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(nm)$，主要开销在遍历棋盘和计算组合数
• 空间复杂度：$O(nm)$，用于存储棋盘状态

样例解释

样例1

输入：
1 5
O....
....O

输出：
0.25

解释：经过大量步数后，系统达到平稳分布，目标状态的概率为 $1/4$。

样例2

输入：
2 2
O.
.O

OO
..

输出：
0

解释：初始状态和目标状态的奇偶性不同，无法通过合法移动达到目标状态。

总结

本题的关键在于理解：

1. 棋盘移动的奇偶性约束
2. 马尔可夫链的平稳分布性质
3. 如何计算状态空间的大小和转移概率

通过组合数学和图论的性质，我们可以高效地计算出经过无限步数后的概率分布。