题解 | #矩形计数#

题目链接

矩形计数

题目描述

给定一个 $N \times M$ 的网格，每个单元格被染成白色（0）或黑色（1）。求满足以下条件的非空单元格集合 $S$ 的数量：

集合中所有单元格颜色相同。
集合中任意两单元格处在同一行或同一列。

结果对 $1,000,000,007$ 取模。

解题思路

本题的核心在于理解“任意两单元格处在同一行或同一列”这一约束。

核心条件分析

这个条件意味着一个有效的集合 $S$ 中的所有单元格，必须全部位于同一行，或者全部位于同一列。任何跨越多行和多列的单元格组合（例如 L 形或 $2 \times 2$ 的矩形）都会存在一对不满足条件的单元格。

因此，问题转化为统计两类集合的总数：

所有单元格都在同一行且颜色相同的非空集合。
所有单元格都在同一列且颜色相同的非空集合。

容斥原理计数

由于颜色相同的要求，我们可以分别计算“全白”集合和“全黑”集合的数量，然后将它们相加。

我们以计算“全白”集合为例，可以使用容斥原理来避免重复计数：

\text{总白集合数} = (\text{行内白集合数}) + (\text{列内白集合数}) - (\text{同时是行内也是列内的白集合数})

一个集合“同时是行内也是列内”，当且仅当它只包含一个单元格。
所以，我们需要减去的重复部分就是单个白色单元格构成的集合的数量，这恰好是网格中白色单元格的总数。

计算步骤

行内集合数：
- 遍历每一行 $i$ 。
- 统计该行白色单元格的数量，记为 $w_i$ 。
- 从这 $w_i$ 个白色单元格中，可以组成 $2^{w_i} - 1$ 个不同的非空子集。
- 将所有行的结果累加，即 $\sum_{i=1}^{N} (2^{w_i} - 1)$ 。
列内集合数：
- 同理，遍历每一列 $j$ ，统计该列白色单元格的数量 $w'_j$ 。
- 总的列内集合数是 $\sum_{j=1}^{M} (2^{w'_j} - 1)$ 。
最终计算：
- 对白色和黑色分别执行上述计算。
- 白色集合总数 = $(\sum_{i=1}^{N} (2^{w_i} - 1)) + (\sum_{j=1}^{M} (2^{w'_j} - 1)) - (\text{白色单元格总数})$
- 黑色集合总数 = $(\sum_{i=1}^{N} (2^{b_i} - 1)) + (\sum_{j=1}^{M} (2^{b'_j} - 1)) - (\text{黑色单元格总数})$
- 最终答案是这两者之和。所有计算都在模 $1,000,000,007$ 下进行。

实现细节

为了高效计算 $2^k$ ，我们可以预计算出 $2$ 的幂次并存储起来。
遍历一次网格，即可统计出每行每列的黑白单元格数量。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

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

    int n, m;
    cin >> n >> m;

    vector<long long> white_row_count(n, 0);
    vector<long long> black_row_count(n, 0);
    vector<long long> white_col_count(m, 0);
    vector<long long> black_col_count(m, 0);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int color;
            cin >> color;
            if (color == 0) {
                white_row_count[i]++;
                white_col_count[j]++;
            } else {
                black_row_count[i]++;
                black_col_count[j]++;
            }
        }
    }

    vector<long long> power_of_2(max(n, m) + 1);
    power_of_2[0] = 1;
    for (int i = 1; i <= max(n, m); ++i) {
        power_of_2[i] = (power_of_2[i - 1] * 2) % MOD;
    }

    long long total_ans = 0;

    // White sets
    long long white_sets = 0;
    long long total_white_cells = 0;
    for (int i = 0; i < n; ++i) {
        white_sets = (white_sets + power_of_2[white_row_count[i]] - 1 + MOD) % MOD;
        total_white_cells += white_row_count[i];
    }
    for (int j = 0; j < m; ++j) {
        white_sets = (white_sets + power_of_2[white_col_count[j]] - 1 + MOD) % MOD;
    }
    white_sets = (white_sets - total_white_cells % MOD + MOD) % MOD;

    // Black sets
    long long black_sets = 0;
    long long total_black_cells = 0;
    for (int i = 0; i < n; ++i) {
        black_sets = (black_sets + power_of_2[black_row_count[i]] - 1 + MOD) % MOD;
        total_black_cells += black_row_count[i];
    }
    for (int j = 0; j < m; ++j) {
        black_sets = (black_sets + power_of_2[black_col_count[j]] - 1 + MOD) % MOD;
    }
    black_sets = (black_sets - total_black_cells % MOD + MOD) % MOD;
    
    total_ans = (white_sets + black_sets) % MOD;

    cout << total_ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        final int MOD = 1000000007;

        long[] white_row_count = new long[n];
        long[] black_row_count = new long[n];
        long[] white_col_count = new long[m];
        long[] black_col_count = new long[m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int color = sc.nextInt();
                if (color == 0) {
                    white_row_count[i]++;
                    white_col_count[j]++;
                } else {
                    black_row_count[i]++;
                    black_col_count[j]++;
                }
            }
        }

        long[] power_of_2 = new long[Math.max(n, m) + 1];
        power_of_2[0] = 1;
        for (int i = 1; i <= Math.max(n, m); i++) {
            power_of_2[i] = (power_of_2[i - 1] * 2) % MOD;
        }

        long total_ans = 0;

        // White sets
        long white_sets = 0;
        long total_white_cells = 0;
        for (int i = 0; i < n; i++) {
            white_sets = (white_sets + power_of_2[(int)white_row_count[i]] - 1 + MOD) % MOD;
            total_white_cells += white_row_count[i];
        }
        for (int j = 0; j < m; j++) {
            white_sets = (white_sets + power_of_2[(int)white_col_count[j]] - 1 + MOD) % MOD;
        }
        white_sets = (white_sets - (total_white_cells % MOD) + MOD) % MOD;

        // Black sets
        long black_sets = 0;
        long total_black_cells = 0;
        for (int i = 0; i < n; i++) {
            black_sets = (black_sets + power_of_2[(int)black_row_count[i]] - 1 + MOD) % MOD;
            total_black_cells += black_row_count[i];
        }
        for (int j = 0; j < m; j++) {
            black_sets = (black_sets + power_of_2[(int)black_col_count[j]] - 1 + MOD) % MOD;
        }
        black_sets = (black_sets - (total_black_cells % MOD) + MOD) % MOD;

        total_ans = (white_sets + black_sets) % MOD;

        System.out.println(total_ans);
    }
}

n, m = map(int, input().split())
MOD = 1000000007

white_row_count = [0] * n
black_row_count = [0] * n
white_col_count = [0] * m
black_col_count = [0] * m

grid = []
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(m):
        if row[j] == 0:
            white_row_count[i] += 1
            white_col_count[j] += 1
        else:
            black_row_count[i] += 1
            black_col_count[j] += 1

power_of_2 = [1] * (max(n, m) + 1)
for i in range(1, max(n, m) + 1):
    power_of_2[i] = (power_of_2[i - 1] * 2) % MOD

total_ans = 0

# White sets
white_sets = 0
total_white_cells = 0
for count in white_row_count:
    white_sets = (white_sets + power_of_2[count] - 1 + MOD) % MOD
    total_white_cells += count
for count in white_col_count:
    white_sets = (white_sets + power_of_2[count] - 1 + MOD) % MOD
white_sets = (white_sets - (total_white_cells % MOD) + MOD) % MOD

# Black sets
black_sets = 0
total_black_cells = 0
for count in black_row_count:
    black_sets = (black_sets + power_of_2[count] - 1 + MOD) % MOD
    total_black_cells += count
for count in black_col_count:
    black_sets = (black_sets + power_of_2[count] - 1 + MOD) % MOD
black_sets = (black_sets - (total_black_cells % MOD) + MOD) % MOD

total_ans = (white_sets + black_sets) % MOD

print(total_ans)

算法及复杂度

算法：组合数学、容斥原理
时间复杂度：我们需要遍历整个 $N \times M$ 网格来统计行列的颜色数量，这需要 $\mathcal{O}(N \cdot M)$ 的时间。预计算 $2$ 的幂次需要 $\mathcal{O}(N+M)$ 。之后的计算循环分别遍历行和列，需要 $\mathcal{O}(N+M)$ 。因此，总时间复杂度由遍历网格主导，为 $\mathcal{O}(N \cdot M)$ 。
空间复杂度：需要数组来存储每行每列的颜色计数，以及预计算的 $2$ 的幂次，总空间复杂度为 $\mathcal{O}(N+M)$ 。