CF1982D Beauty of the mountains

Tag：二维前缀和、裴蜀定理

前置知识

裴蜀定理: 设 \(a\) 与 \(b\) 是两个不等于零的整数，那么对于任意整数 \(x\) 和 \(y\)，满足\(gcd(a,b) \mid ax + by\)，且存在整数解让 \(ax + by = gcd(a,b)\) 成立。

题目描述

给定一个 \(n\) 行 \(m\) 列的矩阵，并且给定每个元素的权值，以及一个数字 \(k\)。给定一个 \(n\) 行 \(m\) 列的 \(01\) 数组，把整个矩形分成两个部分。我们把所有被标记为 \(0\) 的元素的和记为 \(sum_0\)，标记为 \(1\) 的元素的和记为 \(sum_1\)。

现在你有一个 \(k \times k\) 大小的矩阵，可以放在这个 \(n\) 行 \(m\) 列的矩阵上，之后可以把这个 \(k \times k\) 大小的矩阵内的元素增加或减少一个数值。

问是否存在一种方案可以使得若干次操作后 \(sum_0 = sum_1\)。

数据说明：

\(1 \le n, m \le 500, 1 \le k \le min(n, m), a_{i j}\) (\(0 \le a_{i j} \le 10^{9}\)

分析

现在我们假设一个 \(k \times k\) 大小矩阵对一个位置进行操作的时候改变的数值是 \(c\)。我们假设这个矩阵中有 \(a\) 个 \(0\) 和 \(b\) 个 \(1\)。

那么我们一次操作对于 \(sum_0\) 和 \(sum_1\) 产生的影响就分别是 \(c \times a\) 和 \(c \times b\)。

我假设 \(p\) 为 \(k \times k\) 大小的矩阵有多少个可以放置的位置，则可以计算：

\[\begin{equation} p = (n-k+1) \times (m-k+1) \tag{1} \end{equation}\]

那么进一步考虑一下这 \(p\) 种选位以及他们分别选择的 \(c\) 会对 \(sum_0\) 和 \(sum_1\) 产生什么影响：

\[\begin{equation} \Delta sum_0 = c_1 \times a_1 + ... + c_p \times a_p \tag{2} \end{equation}\]

\[\begin{equation} \Delta sum_1 = c_1 \times b_1 + ... + c_p \times b_p \tag{3} \end{equation}\]

我们记 \(sum_0\) 和 \(sum_1\) 经过所有操作之后分别成为 \(ans_0\) 和 \(ans_1\)。则：

\[\begin{equation} ans_0 = sum_0 + \Delta sum_0 \tag{4} \end{equation}\]

\[\begin{equation} ans_1 = sum_1 + \Delta sum_1 \tag{5} \end{equation}\]

由于我们最后的目标就是要让：

\[\begin{equation} ans_0 = ans_1 \tag{6} \end{equation}\]

我们把 \((4)\) 和 \((5)\) 代入 \((6)\) 中：

\[\begin{equation} sum_0 + \Delta sum_0 = sum_1 + \Delta sum_1 \end{equation}\]

移项后可以得到：

\[\begin{equation} sum_0 - sum_1 = \Delta sum_1 - \Delta sum_0 \tag{7} \end{equation}\]

我们又可以根据 \((2)\) 和 \((3)\) 得出：

\[\begin{equation} \Delta sum_1 - \Delta sum_0 = (c_1 \times b_1 + ... + c_p \times b_p) - (c_1 \times a_1 + ... + c_p \times a_p) \end{equation}\]

\[\begin{equation} \Delta sum_1 - \Delta sum_0 = (b_1 - a_1) \times c_1 + ... + (b_p - a_p) \times c_p \tag{8} \end{equation}\]

最后根据 \((7)\) 和 \((8)\) 就可以得到最后的公式：

\[\begin{equation} sum_0 - sum_1 = (b_1 - a_1) \times c_1 + ... + (b_p - a_p) \times c_p \tag{9} \end{equation}\]

得到这个式子之后我们就可以得出最后的结论了，根据裴蜀定理推广，我们就可以得到一个结论，当：

\[\begin{equation} gcd((b_1 - a_1),...,(b_p - a_p)) \mid sum_0 - sum_1 \tag{10} \end{equation}\]

这个式子满足时，对应的一定存在一组 \(c\) 的解。

因为我们要快速查询一个二维区间内的 \(a\) 和 \(b\) 的数量，所以我们要做一个二维前缀和，以此来达到快速查询的目的。

之后我们对于每一个 \(k \times k\) 的区间内 \(0\) 的数量和 \(1\) 的数量的差取 \(\text{gcd}\)。最后我们判断整个二维数组中 \(1\) 和 \(0\) 的关系，以及根据 \((10)\) 来判断是否存在符合答案的解就可以了。

值得一提的是不要忘记特判了最后取完 \(\text{gcd}\) 结果是 \(0\) 的状况，在这种情况下，代表无论 \(k \times k\) 的矩阵放在哪里，区间中 \(0\) 的个数和 \(1\) 的个数永远相等，这样一来我们怎么变换都不会改变其相对关系，所以这种情况下是无解的。

代码实现

void NeverSayNever() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> vec(n + 1, vector<int>(m + 1));
    vector<vector<int>> mp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> vec[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        string str;
        cin >> str;
        str = ' ' + str;
        for (int j = 1; j <= m; ++j) {
            mp[i][j] = str[j] - '0';
        }
    }
    vector g(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
            if (mp[i][j] == 1) {
                g[i][j] += 1;
            }
        }
    }
    int gd = 0;
    for (int i = k; i <= n; ++i) {
        for (int j = k; j <= m; ++j) {
            int tmp = g[i][j] - g[i - k][j] - g[i][j - k] + g[i - k][j - k];
            gd = gcd(gd, abs(k * k - 2 * tmp));
        }
    }
    int sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mp[i][j] == 1) {
                sum2 += vec[i][j];
            } else {
                sum1 += vec[i][j];
            }
        }
    }
    if (sum1 == sum2) {
        cout << "YES" << endl;
        return;
    }
    if (gd != 0) {
        if (abs(sum1 - sum2) % gd == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    } else {
        cout << "NO" << endl;
    }
}

额外思考

感觉这题考的不仅是二维前缀和以及裴蜀定理，比较难的部分是式子的推断以及化简成可以用裴蜀定理来解决的样子，对于数学不敏感以及推式子能力较弱的选手可能会比较难顶。

日志

本页面创建于 2024/06/26 03:30