「Codeforces 1186E」Vus the Cossack and a Field
题目链接: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$。