题目链接：Codeforces 1186E
Vus 有一个 $n \times m$ 的 $01$ 矩阵，他通过如下方法构造了一个无限大的矩阵：
- 计算出当前矩阵的反矩阵。即 $0$ 变成 $1$，$1$ 变成 $0$。
- 将当前矩阵放在左上角和右下角，将反矩阵放在左下角和右上角。
- 将得到的矩阵作为当前矩阵，回到步骤 $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)$ 分为若干部分分别求和，具体如下图所示：
- 左上方的绿色部分：答案为 $n \cdot m \left\lfloor\frac{r \cdot c}{2}\right\rfloor$；如果 $r, c$ 均为奇数，那么对右下角小矩阵分类讨论，根据其正反情况计算答案。
- 左下方、右上方黄色部分：和绿色部分统计方式相同，都是利用两两配对的性质，对于奇数情况同样分类讨论。
- 右下方红色部分：根据其小矩阵正反情况计算答案。
最后还有一个大问题：如何计算一个小矩阵的正反情况？
通过简单的数学归纳我们可以得到：设一个小矩阵的坐标为 $(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;
}