题目链接：LOJ 3083

Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。

对于一个由非负整数构成的矩阵，她定义矩阵的 $\text{AND}​$ 值为矩阵中所有数二进制 $\texttt{AND(&)}​$ 的运算结果；定义矩阵的 $\texttt{OR}​$ 值为矩阵中所有数二进制 $\texttt{OR(|)}​$ 的运算结果。

给定一个 $n \times n$ 的矩阵，她希望求出：

1. 该矩阵的所有子矩阵的 $\texttt{AND}​$ 值之和（所有子矩阵 $\texttt{AND}​$ 值相加的结果）。
2. 该矩阵的所有子矩阵的 $\texttt{OR}​$ 值之和（所有子矩阵 $\texttt{OR}​$ 值相加的结果）。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。

由于答案可能非常的大，你只需要输出答案对 $10 ^ 9 + 7​$ 取模后的结果。

数据范围：$1 \le n \le 10 ^ 3$，$\text{矩阵中的自然数} \le 2 ^ {31} - 1$。

Solution

我们按位考虑，这样矩阵变成了 $01$ 矩阵，对两种运算分开考虑：

• 对于 $\texttt{AND}$ 运算，只有全 $1$ 子矩阵有贡献。
• 对于 $\texttt{OR}$ 运算，只有全 $0$ 子矩阵没有贡献。

直接单调栈找到两类矩阵的数量即可。

时间复杂度：$\mathcal O(n ^ 2 \log w)$，其中 $w$ 为值域。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e3 + 5;
const int P = 1e9 + 7;

int n, a[N][N], h[N][N], l[N], r[N], stk[N];

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
int calc(int *h) {
    int top;
    stk[top = 0] = 0;
    for (int i = 1; i <= n; i++) {
        for (; top && h[i] <= h[stk[top]]; top--);
        l[i] = stk[top];
        stk[++top] = i;
    }
    stk[top = 0] = n + 1;
    for (int i = n; i >= 1; i--) {
        for (; top && h[i] < h[stk[top]]; top--);
        r[i] = stk[top];
        stk[++top] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        add(ans, (i - l[i]) * (r[i] - i) * h[i]);
    }
    return ans;
}
int solve(int v, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            h[i][j] = (((a[i][j] >> k) & 1) == v ? h[i - 1][j] + 1 : 0);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) add(ans, calc(h[i]));
    return ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int tot = 1LL * n * (n + 1) / 2 * n * (n + 1) / 2 % P;
    int ans1 = 0, ans2 = 0;
    for (int k = 0; k < 31; k++) {
        int bin = 1 << k;
        add(ans1, 1LL * bin * solve(1, k) % P);
        add(ans2, 1LL * bin * (tot - solve(0, k) + P) % P);
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}