Moe's CF Life

Appearance

E. She knows... - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 1014 (Div. 2) 标签: combinatorics, constructive algorithms, graphs, math 难度: *2100

题目大意喵~ ​

主人，你好呀！这次的任务是帮 D. Pippy 装饰派对的地板哦，喵~

我们有一个 n x m 的大棋盘，一开始大部分是绿色的。但是呢，有 k 个格子已经被涂上了黑色（用 1 表示）或者白色（用 0 表示）。我们的任务是，把所有剩下的绿色格子也涂成黑色或者白色。

最终的涂色方案需要满足一个奇妙的条件：整个棋盘上，所有相邻（上下左右）且颜色不同的格子对的数量，必须是一个偶数！

我们需要计算出，有多少种涂色方法可以满足这个条件。因为答案可能很大，所以要对 10^9 + 7 取模哦。

输入：

  • n, m: 棋盘的尺寸，可能会非常大呢！
  • k: 已经涂好颜色的格子数量。
  • 接下来 k 行是这些格子的坐标 (x, y) 和颜色 c。

输出：

  • 满足条件的涂色方案数，记得取模哦！

解题思路，一起思考吧！ ​

喵~ 这个问题看起来好复杂，n 和 m 那么大，棋盘根本存不下！但是别担心，遇到这种问题，通常都有巧妙的捷径，关键在于找到问题的核心呐。

关键条件转换 ​

我们要求的核心是“相邻不同色格子对的数量为偶数”。让我们把这个条件用数学语言翻译一下。

令 c(x, y) 表示格子 (x, y) 的颜色（0 或 1）。如果两个相邻格子 p1 和 p2 颜色不同，c(p1) != c(p2)，这等价于 (c(p1) + c(p2)) % 2 == 1。

我们要求的是： Sum_{所有相邻对(p1, p2)} [c(p1) != c(p2)] 是一个偶数。 这等价于： (Sum_{所有相邻对(p1, p2)} (c(p1) + c(p2))) % 2 == 0

这个求和式看起来还是很麻烦。我们换个角度看，一个格子 (x, y) 会在多少个“相邻对”中出现呢？当然是它的邻居数量啦！我们把这个数量记作 deg(x, y) (格子的度)。

于是，上面的和式可以重新组合成对每个格子进行计算： (Sum_{所有格子 p} deg(p) * c(p)) % 2 == 0

度数的神奇作用 ​

现在我们来看看不同位置的格子的度数 deg(p) 是多少：

  1. 角点 (4个): deg = 2 (偶数)
  2. 边上但非角点 (剩下的边界): deg = 3 (奇数)
  3. 内部点: deg = 4 (偶数)

在模2的运算下，偶数乘以任何数都等于0！也就是说，deg(p) * c(p) % 2 当 deg(p) 是偶数时，结果总是0。这意味着角点和内部点的颜色选择，对最终总和的奇偶性完全没有影响！

所以，真正影响奇偶性的，只有那些度数为奇数（也就是3）的格子！这些格子就是所有在棋盘边缘，但又不是角点的格子。我们把这些特殊格子的集合称为 S 吧。

我们的条件就奇迹般地简化为： (Sum_{p in S} 3 * c(p)) % 2 == 0 因为 3 % 2 == 1，所以这等价于： (Sum_{p in S} c(p)) % 2 == 0

哇！也就是说，只要保证集合 S 中所有格子的颜色值（0或1）加起来是偶数，整个棋盘的条件就满足了！太神奇了对不对，喵~？

计算方案数 ​

现在问题变得清晰多啦！我们只需要关注集合 S 里的格子。

  • 集合 S 的大小是 2 * (n - 2) + 2 * (m - 2) = 2 * (n + m - 4)。
  • total_green = n * m - k 是我们可以自由涂色的格子总数。

我们把集合 S 分为两部分：

  1. 已经被涂色的格子。
  2. 还是绿色的格子，我们可以决定它们的颜色。

设 fixed_color_sum 是 S 中那些已经被涂色的格子的颜色之和 (模2)。 设 g 是 S 中绿色格子的数量。

我们需要为这 g 个绿色格子选择颜色，使得它们的颜色之和 green_color_sum 满足： (fixed_color_sum + green_color_sum) % 2 == 0

现在分两种情况讨论：

情况一：g = 0 这意味着 S 中所有格子的颜色都已确定。我们没有任何选择余地了。

  • 如果 fixed_color_sum 恰好是偶数，那么条件满足。我们可以任意涂抹不在S中的绿色格子。这些格子的数量就是 total_green。所以有 2^total_green 种方案。
  • 如果 fixed_color_sum 是奇数，条件永远无法满足。方案数为 0。

情况二：g > 0 我们至少可以决定 S 中一个绿色格子的颜色！

  • 我们可以自由地决定前 g-1 个绿色格子的颜色，有 2^(g-1) 种方式。
  • 对于最后一个（第 g 个）绿色格子，它的颜色是被唯一确定的！为了让 green_color_sum 的奇偶性符合要求，它的颜色只有一种选择（0或1）。
  • 所以，给 S 中的 g 个绿色格子涂色的方案有 2^(g-1) 种。
  • 至于那些不属于S的绿色格子，它们的颜色不影响最终条件，可以随便涂！这样的格子有 total_green - g 个。
  • 总方案数 = (给S中绿色格子涂色的方案) * (给S外绿色格子涂色的方案) = 2^(g-1) * 2^(total_green - g) = 2^(total_green - 1)。

总结一下，我们只需要统计出 S 中有多少预设格子、它们的颜色和是多少，以及 S 中有多少绿色格子，就可以算出答案啦！

代码实现，看这里喵！ ​

cpp
#include <iostream>
using namespace std;

// 快速幂模板，用来计算 a^b % mod，对付大指数超好用！
const long long mod = 1000000007;
long long mod_pow(long long base, long long exponent, long long mod) {
    // 指数是负数的话，在这里我们认为结果是0
    if (exponent < 0) {
        return 0;
    }
    base %= mod;
    long long result = 1;
    while (exponent > 0) {
        if (exponent & 1) 
            result = (result * base) % mod;
        exponent = exponent >> 1;
        base = (base * base) % mod;
    }
    return result;
}

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

    int t;
    cin >> t;
    while (t--) {
        long long n, m;
        int k;
        cin >> n >> m >> k;

        // 我们可以自由涂色的格子总数
        long long total_green = n * m - k;
        
        // 计算特殊集合S的大小，即边上非角点的格子总数
        long long S_size = 2 * (n + m - 4);

        int fixed_in_S_count = 0; // S中已经被涂色的格子数量
        int fixed_color_sum = 0;  // S中已涂色格子的颜色和 (模2)

        for (int i = 0; i < k; i++) {
            long long x, y;
            int c;
            cin >> x >> y >> c;

            // 判断这个格子是不是在集合S里
            // 条件是：在第一行或最后一行，但不在角落
            if (x == 1 || x == n) {
                if (y >= 2 && y <= m - 1) {
                    fixed_in_S_count++;
                    fixed_color_sum = (fixed_color_sum + c) % 2;
                }
            } 
            // 或者：在第一列或最后一列，但不在角落
            else if (y == 1 || y == m) {
                if (x >= 2 && x <= n - 1) {
                    fixed_in_S_count++;
                    fixed_color_sum = (fixed_color_sum + c) % 2;
                }
            }
        }

        // g 是 S 中绿色格子的数量
        long long g = S_size - fixed_in_S_count;
        long long ans;

        if (g == 0) { // 情况一：S中没有绿色格子
            if (fixed_color_sum % 2 == 0) {
                // 颜色和是偶数，满足条件。所有绿色格子都不在S里
                ans = mod_pow(2, total_green, mod);
            } else {
                // 颜色和是奇数，无解
                ans = 0;
            }
        } else { // 情况二：S中至少有一个绿色格子
            // 方案数是 2^(total_green - 1)
            ans = mod_pow(2, total_green - 1, mod);
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(k) 的说。对于每个测试用例，我们主要做的就是遍历 k 个已经涂好颜色的格子。快速幂的计算是 O(log(nm))，因为 n 和 m 很大，所以指数也很大，但对数增长很慢，所以非常快。总的来说，主要开销就是读取和处理 k 个点，所以是 O(k) 级别。
  • 空间复杂度: O(1) 的说。我们没有存储 k 个点的具体信息，只是在读取时进行累加计算，只用了几个变量来记录状态。非常节省空间呢！

知识点与总结 ​

这次的解题之旅真是充满惊喜，喵~ 我们来总结一下学到了什么吧！

  1. 奇偶性分析 (Parity Analysis): 这是解题的屠龙刀！面对看似复杂、要求“数量为偶/奇”的组合问题，优先考虑奇偶性分析。它能把复杂的关系大大简化。
  2. 问题转化: 把“计算相邻不同色对”转化为了“计算带权重的颜色和”，再利用度数的奇偶性，最终简化为只关心一个特定子集 S 的颜色和。这种层层递进的转化是解决难题的关键技巧。
  3. 不受大尺度迷惑: n 和 m 高达 10^9 是个烟雾弹。真正的解法和棋盘的整体大小关系不大，而是和 k 个特殊点的位置有关。这是处理大规模输入问题的常见思路。
  4. 组合计数: 在确定了约束条件后，我们用简单的组合数学思想计算方案数。g > 0 时，g-1 个元素自由选择，第 g 个元素被约束，这是个经典的计数模型。
  5. 模块化编程: 代码中的快速幂 mod_pow 是一个独立的模块，处理大数取模问题，让主逻辑更清晰。

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

Released under the MIT License.

Copyright © 2024-present Moe