§ 题意简述

给定一个 $n\times n$ 的矩阵，有 $n\times n$ 个内容全部为 $1,2,\cdots,n\times n$ 的子矩阵。用子矩阵覆盖大矩阵，求第一个覆盖的子矩阵的所有可能方案数。

§ 题解

挺水一道题。

归纳一下，我们可以发现题目就是让我们求 $n\times n$ 减去不可能的子矩阵数。

考虑如何判断一个子矩阵不可能第一个覆盖。

容易发现一个子矩阵一旦出现在了 本应是其他子矩阵覆盖的范围 那么我们就可以断言这个子矩阵不可能是第一个覆盖的子矩阵。

那么如何统计呢？很简单，找出每个子矩阵的左上右下两个端点然后二维前缀和即可。

有几点需要注意一下：

• 端点被覆盖了其实是不影响的，我们只需要关注露出来的端点即可。

• 当 $n\neq 1$ 时，只有一种颜色在最上层的情况也是不可能的，需要特判一下。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 1e3 + 5;
int impossible, n, mat[MAXN][MAXN], sum[MAXN][MAXN];
int color[MAXN * MAXN][5], mark[MAXN][MAXN], vis[MAXN * MAXN], tot;

void prepare() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			scanf("%d", &mat[i][j]);
		}
	}
	for (int i = 1; i <= n * n; ++i) color[i][0] = color[i][1] = 10086001;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (mat[i][j]) {
				if (color[mat[i][j]][0] == 10086001) ++tot;
				color[mat[i][j]][0] = min(i, color[mat[i][j]][0]);
				color[mat[i][j]][1] = min(j, color[mat[i][j]][1]);
				color[mat[i][j]][2] = max(i, color[mat[i][j]][2]);
				color[mat[i][j]][3] = max(j, color[mat[i][j]][3]);
			}
		}
	}
}

void work() {
	for (int i = 1; i <= n * n; ++i) {
		if (color[i][0] ^ 10086001) {
			mark[color[i][0]][color[i][1]]++;
			mark[color[i][2] + 1][color[i][3] + 1]++;
			mark[color[i][0]][color[i][3] + 1]--;
			mark[color[i][2] + 1][color[i][1]]--;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			sum[i][j] = mark[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
}

void answer() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (mat[i][j] && sum[i][j] > 1 && vis[mat[i][j]] ^ 1) {
				vis[mat[i][j]] ^= 1;
				impossible++;
			}
		}
	}
	printf("%d\n", n * n - impossible - (tot == 1 && n != 1));
}

signed main() {
	prepare();
	work();
	answer();
}