CF1982D Beauty of the mountains

传送门

Solution

设有雪顶和无雪顶的山的总高度差为 $c$。

通过计算代表山峰类型的 $01$ 矩阵的二维前缀和，可以求出每个大小为 $k\times k$ 的方形区域中，两种类型的山的数量差。设每个方形的数量差分别为 $a_i$，则问题转换为方程

$\sum a_ix_i=c$

是否有整数解。$x_i$ 表示对在 $a_i$ 所在的方形内所有的山削减（或增加）多少高度。为方便计算，不妨对所有 $a_i$ 及 $c$ 取绝对值，不影响做法正确性。

此时方程符合多元线性丢番图方程的形式。根据定理，方程有解当且仅当

$\gcd(a_1,a_2,\cdot \cdot \cdot,a_n)|c$

定理证明可参考《初等数论及其应用》 ([美] Kenneth H·Rosen) 第 103 页定理 3.24 的证明，此处略。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;

ll T, n, m, k, a[N][N], sum[N][N], tot, ans, b[N][N];
char str[N];

void solve()
{
	tot = ans = 0;
	scanf("%lld%lld%lld", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			sum[i][j] = 0;
		}
			
	for (int i = 1; i <= n; i++) {
		scanf("%s", str + 1);
		for (int j = 1; j <= m; j++) {
			a[i][j] *= (str[j] == '0' ? -1 : 1);
			b[i][j] = (str[j] == '0' ? -1 : 1);
			tot += a[i][j];
		}
	}
	tot = abs(tot);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			sum[i][j] = sum[i][j - 1] + b[i][j];
			if (j > k) 
				sum[i][j] -= b[i][j - k];
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			sum[i][j] += sum[i - 1][j];
		for (int i = n; i > k; i--)
			sum[i][j] -= sum[i - k][j];
	}
	for (int i = k; i <= n; i++) 
		for (int j = k; j <= m; j++)
			if (sum[i][j])
				ans = sum[i][j];
	if (ans == 0) {
		if (tot == 0)
			printf("YES\n");
		else 
			printf("NO\n");
		return;
	} 
	for (int i = k; i <= n; i++)
		for (int j = k; j <= m; j++) 
			if (sum[i][j])
				ans = __gcd(ans, abs(sum[i][j]));
	if (tot % ans == 0)
		printf("YES\n");
	else
		printf("NO\n");
}

int main()
{
	scanf("%lld", &T);
	while (T--) solve();
	return 0;
}