F. Balanced Domino Placements - 题解

比赛与标签

比赛: Codeforces Global Round 5 标签: combinatorics, dp 难度: *2600

题目大意喵~

主人你好呀~！这道题是关于在一个 h x w 的网格里放置多米诺骨牌的计数问题，喵~

题目给了我们一个初始状态，上面已经放了一些多米诺骨牌。这种放置方式被称为“完美平衡”的，它的意思是：任何一行或一列，要么没有被骨牌覆盖的格子，要么只有一个格子被覆盖，要么有两个格子被覆盖，且这两个格子必须属于同一个多米诺骨牌。

我们的任务是，在初始状态的基础上，再放置零个或多个新的多米诺骨牌，使得最终的布局依然是“完美平衡”的。我们需要计算出有多少种不同的放置方案，并将结果对 998244353 取模，的说。

简单来说，就是在一个满足特定规则的棋盘上，计算增加骨牌后仍然满足规则的方案数，呐。

解题思路大揭秘！

喵哈哈，这道题看起来有点复杂，但只要我们抓住核心，就能把它分解成可爱的小问题！关键就在于理解“完美平衡”这个条件的真正含义，的说。

1. 核心思想：解耦行与列的决策喵~

“完美平衡”这个规则限制了每一行和每一列的状态。我们来分析一下：

• 对于任意一行：它要么完全空闲，要么可以容纳一个水平多米诺（占据该行的两个格子），要么可以容纳若干个竖直多米诺的“一半”（每个竖直多米诺占据该行的一个格子）。但是，一行之内不能既有水平多米诺，又有竖直多米诺的一部分，因为那样会违反规则（比如一个水平的占两格，一个竖直的占一格，总共三个格子被占了）。
• 同理，对于任意一列：它要么完全空闲，要么可以容纳一个竖直多米诺（占据该列的两个格子），要么可以容纳若干个水平多米诺的“一半”。

这个观察太重要啦！它告诉我们，放置水平多米诺和放置竖直多米诺的决策在很大程度上是独立的。我们可以分别考虑放置多少个水平多米诺和多少个竖直多米诺，然后把方案数组合起来！

2. 状态分解与DP计数

我们可以枚举新放置的水平多米诺数量 j 和竖直多米诺数量 i。总方案数就是所有合法的 (i, j) 组合的方案数之和。

总方案数 = Σ (放置 i 个竖直多米诺 和 j 个水平多米诺的方案数)

现在问题变成了，如何计算特定 i 和 j 的方案数呢？

• 放置 i 个竖直多米诺：

  1. 我们需要 i 对相邻且都未被占用的行来放置它们。
  2. 我们还需要 i 个未被占用的列来放置它们。

• 放置 j 个水平多米诺：

  1. 我们需要 j 对相邻且都未被占用的列来放置它们。
  2. 我们还需要 j 个未被占用的行来放置它们。

我们可以用动态规划来解决“选择k对相邻且未被占用的行/列”这个问题！

我们定义 f[k][p] 为：在前 k 行中，选择 p 对不重叠的、相邻且均为空闲的行的方案数。 状态转移方程就是：

• 不选择第 k 行与第 k-1 行配对：方案数来自前 k-1 行，即 f[k-1][p]。
• 选择第 k 行与第 k-1 行配对（前提是这两行都空闲）：方案数来自前 k-2 行选 p-1 对，即 f[k-2][p-1]。 所以，f[k][p] = f[k-1][p] + f[k-2][p-1]。这是一个非常经典的DP模型呢！

同理，我们可以定义 g[k][p] 为在前 k 列中选择 p 对不重叠的、相邻且均为空闲的列的方案数，转移方程完全一样。

3. 组合计数大法！

通过DP，我们得到了：

• f[h][i]：从 h 行中选择 i 对相邻空闲行（用于竖直多米诺）的方案数。
• g[w][j]：从 w 列中选择 j 对相邻空闲列（用于水平多米诺）的方案数。

接下来就是把它们“安排”到具体的位置上！

1. 首先，我们扫描一遍初始布局，标记出所有已经被占用的行和列，并计算出空闲行数 free_rows 和空闲列数 free_cols。
2. 假设我们决定放置 i 个竖直多米诺和 j 个水平多米诺。
3. 安排水平多米诺：我们已经通过 g[w][j] 选好了 j 对列。现在需要为它们选择 j 个栖身之所——也就是 j 个空闲行。总共有 free_rows 个空闲行，但其中有 2*i 个行已经被我们预定给竖直多米诺了。所以我们能用的行还剩 free_rows - 2*i 个。从这么多行里选 j 个出来，并且顺序是重要的（放在第1行和第2行是不同的方案），所以是排列数 P(free_rows - 2*i, j)。
4. 安排竖直多米诺：同理，我们已经通过 f[h][i] 选好了 i 对行。现在需要为它们选择 i 个空闲列。总共有 free_cols 个空闲列，但其中 2*j 个列已经被水平多米诺预定了。所以我们能用的列还剩 free_cols - 2*j 个。方案数就是排列数 P(free_cols - 2*j, i)。

4. 最终公式

把所有部分乘起来，再对所有可能的 i 和 j 求和，就是最终答案啦！ ans = Σ (f[h][i] * g[w][j] * P(free_rows - 2*i, j) * P(free_cols - 2*j, i))

求和的条件是：

• 2*i + j <= free_rows (总共用掉的行数不能超过空闲行数)
• 2*j + i <= free_cols (总共用掉的列数不能超过空闲列数)

这样，我们就把一个复杂的问题变成DP和组合计数的拼接了，是不是很清晰了呢，喵~

代码实现详解喵

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 998244353;

// 快速幂，用来求逆元喵~
ll pow_mod(ll base, ll exp, ll modulus) {
    ll result = 1;
    base %= modulus;
    while (exp > 0) {
        if (exp & 1) 
            result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int h, w, n;
    cin >> h >> w >> n;

    // 用 vx 和 vy 数组标记已经被初始多米诺占用的行和列
    vector<bool> vx(h + 1, false);
    vector<bool> vy(w + 1, false);
    for (int i = 0; i < n; i++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        vx[r1] = true;
        vx[r2] = true;
        vy[c1] = true;
        vy[c2] = true;
    }

    // 计算空闲的行数和列数
    int cnt1 = 0;
    for (int i = 1; i <= h; i++) {
        if (vx[i]) cnt1++;
    }
    int cnt2 = 0;
    for (int i = 1; i <= w; i++) {
        if (vy[i]) cnt2++;
    }
    int free_rows = h - cnt1;
    int free_cols = w - cnt2;

    int mx_dim = max(h, w);
    // 预处理阶乘和阶乘逆元，方便计算排列数
    vector<ll> fac(mx_dim + 1);
    vector<ll> inv_fac(mx_dim + 1);
    fac[0] = 1;
    for (int i = 1; i <= mx_dim; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv_fac[mx_dim] = pow_mod(fac[mx_dim], mod - 2, mod);
    for (int i = mx_dim - 1; i >= 0; i--) {
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
    }

    // 计算排列数 P(n, k) = n! / (n-k)!
    auto perm = [&](int n_val, int k_val) -> ll {
        if (k_val < 0 || k_val > n_val) return 0;
        return fac[n_val] * inv_fac[n_val - k_val] % mod;
    };

    // DP 计算 f[i][j]: 在前 i 行中选择 j 对相邻空闲行的方案数
    vector<vector<ll>> f(h + 1, vector<ll>(mx_dim + 1, 0));
    f[0][0] = 1;
    for (int i = 1; i <= h; i++) {
        for (int j = 0; j <= i / 2; j++) { // j 最多是 i/2，小优化
            f[i][j] = f[i - 1][j]; // 不选第 i 行
            if (i >= 2 && j >= 1 && !vx[i] && !vx[i - 1]) { // 如果 i 和 i-1 行都空闲，可以配对
                f[i][j] = (f[i][j] + f[i - 2][j - 1]) % mod;
            }
        }
    }

    // DP 计算 g[i][j]: 在前 i 列中选择 j 对相邻空闲列的方案数
    vector<vector<ll>> g(w + 1, vector<ll>(mx_dim + 1, 0));
    g[0][0] = 1;
    for (int i = 1; i <= w; i++) {
        for (int j = 0; j <= i / 2; j++) { // j 最多是 i/2
            g[i][j] = g[i - 1][j]; // 不选第 i 列
            if (i >= 2 && j >= 1 && !vy[i] && !vy[i - 1]) { // 如果 i 和 i-1 列都空闲，可以配对
                g[i][j] = (g[i][j] + g[i - 2][j - 1]) % mod;
            }
        }
    }

    // 遍历所有可能的竖直(i)和水平(j)多米诺数量，累加方案数
    ll ans = 0;
    for (int i = 0; i <= free_rows / 2; i++) { // i 是竖直多米诺数
        for (int j = 0; j <= free_cols / 2; j++) { // j 是水平多米诺数
            // 检查资源是否足够
            if (2 * i + j <= free_rows && 2 * j + i <= free_cols) {
                ll term = f[h][i] * g[w][j] % mod;
                // P(free_rows - 2*i, j): 为 j 个水平多米诺分配行
                term = term * perm(free_rows - 2 * i, j) % mod;
                // P(free_cols - 2*j, i): 为 i 个竖直多米诺分配列
                term = term * perm(free_cols - 2 * j, i) % mod;
                ans = (ans + term) % mod;
            }
        }
    }
    ans = (ans % mod + mod) % mod;
    cout << ans << endl;
    return 0;
}

复杂度分析的说

• 时间复杂度: O(h² + w²) 的说。
  • 预处理阶乘和逆元需要 O(max(h, w))。
  • DP计算 f 表需要 O(h * (h/2)) = O(h²)。
  • DP计算 g 表需要 O(w * (w/2)) = O(w²)。
  • 最后的双重循环遍历 i 和 j，i 的范围是 0 到 h/2，j 的范围是 0 到 w/2，所以这部分是 O(h * w)。
  • 总体来看，复杂度由DP部分主导，为 O(h² + w²)。对于 h, w <= 3600，这个复杂度是可以接受的，喵~
• 空间复杂度: O(h² + w²) 的说。
  • DP表 f 和 g 是主要的空间开销。f 的大小是 O(h * (h/2))，g 的大小是 O(w * (w/2))。所以总空间复杂度是 O(h² + w²)。

知识点与总结

这道题是一道非常棒的组合计数与动态规划结合的题目，它教会了我们几件重要的事情呐：

1. 解耦思想 (Decoupling)：面对看似复杂的约束条件，尝试分析其内在结构，找到可以把问题分解成独立或半独立子问题的方法。这道题里，行和列的决策解耦是解题的关键！
2. 动态规划 (DP)：对于“在n个物品中选k个不相邻/相邻对”这类问题，DP是一个非常强大的工具。f[i][j] = f[i-1][j] + f[i-2][j-1] 是一个需要记在小本本上的经典模型哦。
3. 组合数学 (Combinatorics)：当问题涉及到“选择”和“排列”时，要熟练运用排列组合公式。这道题里，我们先用DP计算了“选择位置组合”的方案数，再用排列数计算了“分配具体位置”的方案数，思路非常清晰。
4. 预处理：在组合计数问题中，如果需要大量计算组合数或排列数，预处理阶乘和阶乘逆元是提高效率的标准操作。

希望这篇题解能帮助到主人哦！继续加油，算法的世界还有更多有趣的冒险在等着我们呢，喵~！