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;
}