题解 | #矩形计数#
矩形计数
https://www.nowcoder.com/practice/0ece8b3002c94320b8866ff0fc5d5fe0
题目链接
题目描述
给定一个 的网格，每个单元格被染成白色（0）或黑色（1）。
需要计算满足以下条件的非空单元格集合的数量：
- 集合中所有单元格颜色相同。
- 集合中任意两个单元格处在同一行或同一列。
结果对 取模。
输入:
- 第一行输入两个整数
。
- 接下来
行，每行
个整数（0或1），以空格分隔。
输出:
- 输出一个整数，表示满足条件的集合数量对
取模的结果。
解题思路
这道题的关键在于理解第二个条件：“集合中任意两个单元格处在同一行或同一列”。
如果一个集合中包含了不在同一行也不同一列的两个点，比如 和
其中
且
，那么这个集合就不满足条件。
因此，一个满足条件的集合，其所有单元格必须全部在同一行内，或者全部在同一列内。
这个问题就转化成了计算两类集合的并集：
- A: 全在同一行内的、同色的、非空集合。
- B: 全在同一列内的、同色的、非空集合。
根据容斥原理，所求答案为 。
-
计算
(行内集合总数)
- 我们可以遍历每一行，独立计算该行能贡献多少个满足条件的集合。
- 对于第
行，假设有
个白色单元格和
个黑色单元格（
）。
- 从这
个子集。由于集合必须非空，所以白色集合有
个。
- 同理，黑色集合有
个。
- 因此，第
个集合。
- 将所有行贡献的集合数加起来，就得到
。
-
计算
(列内集合总数)
- 这个计算与行完全对称。
- 对于第
列，假设有
个白色单元格和
个黑色单元格（
）。
- 第
个集合。
。
-
计算
(交集)
- 一个集合同时属于
和
是什么情况？
- 这意味着该集合的所有单元格必须在同一行内，并且在同一列内。
- 这只可能在集合只包含一个单元格时成立。
- 所以，交集就是所有单个单元格组成的集合。
- 网格中总共有
个单元格，因此就有
- 每个单格集合，在计算
。
- 一个集合同时属于
-
汇总
- 最终答案 =
。
- 由于
需要使用快速幂，或预先计算好2的幂次。所有计算都在模
- 最终答案 =
代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
vector<LL> pow2(max(n, m) + 1);
pow2[0] = 1;
for (int i = 1; i <= max(n, m); ++i) {
pow2[i] = (pow2[i - 1] * 2) % MOD;
}
LL ans = 0;
// 行
for (int i = 0; i < n; ++i) {
int white_count = 0, black_count = 0;
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 0) white_count++;
else black_count++;
}
ans = (ans + pow2[white_count] - 1 + MOD) % MOD;
ans = (ans + pow2[black_count] - 1 + MOD) % MOD;
}
// 列
for (int j = 0; j < m; ++j) {
int white_count = 0, black_count = 0;
for (int i = 0; i < n; ++i) {
if (grid[i][j] == 0) white_count++;
else black_count++;
}
ans = (ans + pow2[white_count] - 1 + MOD) % MOD;
ans = (ans + pow2[black_count] - 1 + MOD) % MOD;
}
// 减去交集
LL intersection = (LL)n * m % MOD;
ans = (ans - intersection + MOD) % MOD;
cout << ans << '\n';
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();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = sc.nextInt();
}
}
final int MOD = 1_000_000_007;
long[] pow2 = new long[Math.max(n, m) + 1];
pow2[0] = 1;
for (int i = 1; i < pow2.length; i++) {
pow2[i] = (pow2[i - 1] * 2) % MOD;
}
long ans = 0;
// 行
for (int i = 0; i < n; i++) {
int whiteCount = 0, blackCount = 0;
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0) whiteCount++;
else blackCount++;
}
ans = (ans + pow2[whiteCount] - 1 + MOD) % MOD;
ans = (ans + pow2[blackCount] - 1 + MOD) % MOD;
}
// 列
for (int j = 0; j < m; j++) {
int whiteCount = 0, blackCount = 0;
for (int i = 0; i < n; i++) {
if (grid[i][j] == 0) whiteCount++;
else blackCount++;
}
ans = (ans + pow2[whiteCount] - 1 + MOD) % MOD;
ans = (ans + pow2[blackCount] - 1 + MOD) % MOD;
}
// 减去交集
long intersection = (long) n * m % MOD;
ans = (ans - intersection + MOD) % MOD;
System.out.println(ans);
}
}
MOD = 1_000_000_007
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
pow2 = [1] * (max(n, m) + 1)
for i in range(1, max(n, m) + 1):
pow2[i] = (pow2[i-1] * 2) % MOD
ans = 0
# 行
for i in range(n):
white_count = grid[i].count(0)
black_count = m - white_count
ans = (ans + pow2[white_count] - 1 + MOD) % MOD
ans = (ans + pow2[black_count] - 1 + MOD) % MOD
# 列
for j in range(m):
white_count = 0
for i in range(n):
if grid[i][j] == 0:
white_count += 1
black_count = n - white_count
ans = (ans + pow2[white_count] - 1 + MOD) % MOD
ans = (ans + pow2[black_count] - 1 + MOD) % MOD
# 减去交集
intersection = (n * m) % MOD
ans = (ans - intersection + MOD) % MOD
print(ans)
算法及复杂度
- 算法：容斥原理、组合计数
- 时间复杂度：
，主要开销在于读取和遍历网格。预计算2的幂次需要
。
- 空间复杂度：
哔哩哔哩公司福利 765人发布