「Codeforces 1186E」Vus the Cossack and a Field

题目链接:Codeforces 1186E

Vus 有一个 $n \times m$ 的 $01$ 矩阵,他通过如下方法构造了一个无限大的矩阵:

  1. 计算出当前矩阵的反矩阵。即 $0$ 变成 $1$,$1$ 变成 $0$。
  2. 将当前矩阵放在左上角和右下角,将反矩阵放在左下角和右上角。
  3. 将得到的矩阵作为当前矩阵,回到步骤 $1$ 并不断重复。

我们将列从上到下标号为 $1$ 到 $\infty$,将行从左到右标号为 $1$ 到 $\infty$。接下来进行 $q$ 次询问,每次询问子矩阵 $(x_1, y_1, x_2, y_2)$ 的元素之和。

数据范围:$1 \le n, m \le 1000$,$1 \le q \le 10 ^ 5$,$1 \le x_1 \le x_2 \le 10 ^ 9$,$1 \le y_1 \le y_2 \le 10 ^ 9$。


Solution

首先进行一个转化,将 $(x_1, y_1, x_2, y_2)$ 转化为 $4$ 个前缀子矩阵相加减的和,那么问题转化为求子矩阵 $(1, 1, x, y)$ 的和。

我们把每个 $n \times m$ 的小矩阵(包括原矩阵和反矩阵)看做一个整体。为了方便表述,矩阵从上到下、从左到右标号为 $0$ 到 $\infty$(注意不是从 $1$ 开始标号),那么元素 $(x, y)$ 所在的小矩阵为:

$$ \left(\frac{x - 1}{n}, \frac{y - 1}{m}\right) $$

设原矩阵为「$0$」,反矩阵为「$1$」,那么若干次操作得到的矩阵为:

$$ \begin{array}{} 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \end{array} $$

我们发现对于任意一行(一列),从左往右(从上往下)每两个分一组,每组内一定是 $0$ 和 $1$ 各一个,即两两匹配。于是我们得到:对于任何一个包含完整小矩阵的前缀矩阵,原矩阵和反矩阵的数量「几乎」相同。

所谓「几乎」一定意味着有特殊情况。对于奇数个小矩阵的前缀大矩阵,最右下角的一个小矩阵是不确定的;但是排除这个小矩阵后,其余小矩阵一定两两匹配!

设 $(x, y)$ 所在小矩阵为 $\left(r = \frac{x - 1}{n}, c = \frac{y - 1}{m}\right)$,我们将前缀矩阵 $(1, 1, x, y)$ 分为若干部分分别求和,具体如下图所示:

  1. 左上方的绿色部分:答案为 $n \cdot m \left\lfloor\frac{r \cdot c}{2}\right\rfloor$;如果 $r, c$ 均为奇数,那么对右下角小矩阵分类讨论,根据其正反情况计算答案。
  2. 左下方、右上方黄色部分:和绿色部分统计方式相同,都是利用两两配对的性质,对于奇数情况同样分类讨论。
  3. 右下方红色部分:根据其小矩阵正反情况计算答案。

最后还有一个大问题:如何计算一个小矩阵的正反情况?

通过简单的数学归纳我们可以得到:设一个小矩阵的坐标为 $(x, y)$,在此特别强调从 $0$ 开始计数(例如上图绿色部分的右下角矩阵坐标为 $(2, 2)$),如果 $\text{bitcount}(x) + \text{bitcount}(y)$ 为奇数,那么该小矩阵为反矩阵

时间复杂度:$\mathcal O(nm + q)$。


Code

#include <cstdio>
 
const int N = 1e3 + 5;
 
int n, m, q, sum[N][N];
 
int opt(int x, int y) {
    return (__builtin_popcount(x) + __builtin_popcount(y)) & 1;
}
int calc(int x, int y, int opt) {
    return opt == 0 ? sum[x][y] : x * y - sum[x][y];
}
long long I(int x, int y, int r, int c) {
    long long ans = 1LL * r * c / 2 * n * m;
    if ((r & 1) && (c & 1)) ans += calc(n, m, opt(r - 1, c - 1));
    return ans;
}
long long D(int x, int y, int r, int c) {
    int xx = r * n;
    long long ans = 1LL * c / 2 * (x - xx) * m;
    if (c & 1) ans += calc(x - xx, m, opt(r, c - 1));
    return ans;
}
long long R(int x, int y, int r, int c) {
    int yy = c * m;
    long long ans = 1LL * r / 2 * n * (y - yy);
    if (r & 1) ans += calc(n, y - yy, opt(r - 1, c));
    return ans;
}
long long O(int x, int y, int r, int c) {
    int xx = r * n, yy = c * m;
    return calc(x - xx, y - yy, opt(r, c));
}
long long query(int x, int y) {
    if (x == 0 || y == 0) return 0;
    int r = (x - 1) / n, c = (y - 1) / m;
    if (r == 0 && c == 0) return O(x, y, r, c);
    if (r == 0) return D(x, y, r, c) + O(x, y, r, c);
    if (c == 0) return R(x, y, r, c) + O(x, y, r, c);
    return I(x, y, r, c) + D(x, y, r, c) + R(x, y, r, c) + O(x, y, r, c);
}
long long query(int x1, int y1, int x2, int y2) {
    return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%1d", &x);
            sum[i][j] = x + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= q; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%lld\n", query(x1, y1, x2, y2));
    }
    return 0;
}

发表评论