题目描述

给定一个 $N \times N$ 的矩阵，你需要求出

1. 该矩阵中所有子矩阵的 $\texttt{AND}$ 值之和
2. 该矩阵中所有子矩阵的 $\texttt{OR}$ 值之和

答案对 $10 ^ 9 + 7$ 取模。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行 $N$ 个自然数，描述矩阵。

输出格式

输出两个自然数，分别表示该矩阵的所有子矩阵的 $\texttt{AND}$ 值之和与 $\texttt{OR}$ 值之和，答案对 $10 ^ 9 + 7$ 取模。

数据范围

$1 \leq N \leq 1000$

对于矩阵中的任意一数 $x$，保证 $0 \leq x < 2 ^ {31}$

输入样例1

3
1 0 0
0 0 0
0 0 0

输出样例1

1 9

输入样例2

3
1 2 3
4 5 6
7 8 9

输出样例2

73 314

算法

(位运算,暴力,单调栈,悬线DP) $O(n ^ 2)$

设原矩阵中第 $i$ 行第 $j$ 个元素为 $b _ {i, j}$。

先考虑如何计算 $\texttt{AND}$。

因为矩阵中每个数做多有 $31$ 位，因此我们可以从 $0$ 到 $31$ 枚举每一位。

对于第 $k$ 位，把原矩阵的第 $k$ 位抠出来，得到一个 $01$ 矩阵。

对于该矩阵中任意一个子矩阵，若该子矩阵中所有元素都是 $1$，则该矩阵的 $\texttt{AND}$ 值为 $1$，否则为 $0$。

接下来，问题转化为：给定一个 $01$ 矩阵，求该矩阵中有多少个子矩阵，满足该子矩阵中所有元素都是 $1$。

而子矩阵可以通过两个属性确定：左上角坐标和右下角坐标。

对于这种问题，我们通常的做法是枚举一个属性，然后考虑如何快速求出合法的另一属性数量。 老套路了

本题中，我们可以枚举右下角坐标，考虑如何快速求出有多少个右上角坐标满足条件。

这个可以用单调栈求，但不太容易想到。

从上往下依次考虑每一行，假设当前考虑到了第 $k$ 行。

对于第 $k$ 行中第 $k$ 个元素 $b _ {k, i}$，记 $f _ {k, i}$ 表示从该元素开始往上数，有多少个连续的 $1$（包括该元素）。

比如矩阵 $b = \left\[ \begin {matrix} 0 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 0 & 0 & 0 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ \end {matrix} \right\] $ 时，$f = \left\[ \begin {matrix} 0 & 1 & 1 & 1 & 1 \\\ 1 & 2 & 2 & 2 & 2 \\\ 0 & 0 & 0 & 3 & 3 \\\ 1 & 1 & 1 & 4 & 4 \\\ 2 & 2 & 2 & 5 & 5 \\\ \end {matrix} \right\] $。

记 $f _ k$ 表示 $f$ 的第 $k$ 行。

则 $f _ k$ 中，包含了所有 $\texttt{AND}$ 值可能为 $1$ 的右下角坐标的信息。

假设我们当前枚举到的右下坐标是 $(k, i)$，考虑此时可取到的左上角的坐标范围。

这个可以 $\text{DP}$，记 $g _ i$ 表示当我们枚举到的右下角坐标为 $(k, i)$ 时，左上角的坐标范围。

设左上角坐标为 $(k - x + 1, y)$。

那么我们可以将状态划分为如下两个集合：

1. 当 $x = f _ {k, i}$ 时
2. 剩下的

至于为什么这么划分，是因为当 $x = f _ {k, i}$ 时的部分，可以用单调栈快速计算，这个后面会写到。

考虑当 $x$ 取到 $f _ {k, i}$ 时，$y$ 的取值范围。

因为 $x$ 取到了 $f _ {k, i}$，所以对于任意 $y \leq j \leq i$ 的 $j$ 而言，都有 $f _ {k, j} \geq f _ {k, i}$。

那么能取到的最小的 $y$，就是 $f _ k$ 中从 $i$ 往左数，最后一个的 $\geq f _ {k, i}$ 的数的位置。

也就是 $f _ k$ 中从 $i$ 往左数，第一个的 $< f _ {k, i}$ 的数的位置 $ + 1$。

记 $l _ i$ 表示第一个的 $< f _ {k, i}$ 的数的位置，那么整个左上角为 $(k - f _ {k, i} + 1, l _ i + 1)$，右下角为 $(k, i)$ 的子矩阵中，所有元素都是 $1$。

我们固定了右下角坐标为 $(k, i)$，而在该子矩阵中，我们可以任取一个位置作为子矩阵左上角，该子矩阵中的元素都是 $1$。

那么当 $x = f _ {k, i}$ 时，对 $g _ i$ 的贡献，即为 $f _ {k, i} \times (i - l _ i)$。

而 $l _ i$ 可以使用单调栈快速计算，这样就可以快速求出当 $x = f _ {k, i}$ 时对 $g _ i$ 的贡献了。

考虑如何计算出剩下的部分。

对于剩下的部分，有 $y \leq l _ i$。

因此剩下的左上角的坐标范围，即为原左上角坐标为 $(k - x + 1, y)$，加上一个 $y \leq l _ i$ 的限制。

不难发现这部分恰好就是 $g _ {l _ i}$，因为当我们考虑以 $(k, l _ i)$ 为右下角坐标的矩阵时，左上角坐标的 $y$ 的范围必然有 $y \leq l _ i$。

那么就得到了转移方程 $g _ i = g _ {l _ i} + f _ {k, i} \times (i - l _ i)$。

这么说可能比较抽象，这里用上述例子中的矩阵 $b _ {5, 5}$ 作为 $(k, i)$ 为例（即 $k = 5, i = 5$ 时）。

当 $k = 5$ 时，$f _ k = [\begin {matrix} 2 & 2 & 2 & 5 & 5 \end {matrix}]$，表示我们当前考虑矩阵 $ \left\[ \begin {matrix} & & & 1 & 1 \\\ & & & 1 & 1 \\\ & & & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ \end {matrix} \right\] $。

$i = 5$ 表示我们当前考虑以如下矩阵中，以蓝色位置为右下角的，所有与值为 $1$ 的矩阵 $ \left\[ \begin {matrix} & & & 1 & 1 \\\ & & & 1 & 1 \\\ & & & 1 & 1 \\\ 1 & 1 & 1 & 1 & 1 \\\ 1 & 1 & 1 & 1 & \color{blue} 1 \\\ \end {matrix} \right\] $。

$f _ {k, i} \times (i - l _ i)$ 表示以下矩阵中红色部分对 $g _ 5$ 的贡献，$g _ {l _ 5 = 3}$ 表示黑色部分对 $g _ 5$ 的贡献。

$ \left\[ \begin {matrix} & & & \color{red} 1 & \color{red} 1 \\\ & & & \color{red} 1 & \color{red} 1 \\\ & & & \color{red} 1 & \color{red} 1 \\\ 1 & 1 & 1 & \color{red} 1 & \color{red} 1 \\\ 1 & 1 & 1 & \color{red} 1 & \color{red} 1 \\\ \end {matrix} \right\] $

这样我们就可以线性计算出所有的 $g$，然后计入答案了。

接下来考虑如何计算 $\texttt{OR}$ 和。

观察 $\texttt{AND}$ 运算和 $\texttt{OR}$ 运算的真值表：

可以发现，$¬(a \texttt{ OR } b) = ¬a \texttt{ AND } ¬b$。（这个从逻辑上也很好理解啦）

根据这个公式，我们可以先将矩阵中所有元素取反（即异或 $1$），然后计算 $\texttt{AND}$，得到所有 $\texttt{OR}$ 为 $0$ 的子矩阵个数。

再用原矩阵中总共的子矩阵个数，减去 $\texttt{OR}$ 为 $0$ 的子矩阵个数，即可得到 $\texttt{OR}$ 为 $1$ 的子矩阵个数。

考虑一个 $N \times N$ 的矩阵，有多少子矩阵。

对于该矩阵的每个子矩阵，我们可以用左上角坐标和右下角坐标确定。

设两个坐标分别为 $(x _ 1, y _ 1), (x _ 2, y _ 2)$，分别考虑这两个坐标中 $4$ 个元素的取值范围。

对于每个 $x _ 2, y _ 2$，左上角坐标必须满足 $x _ 1 \leq x _ 2, y _ 1 \leq y _ 2$。

那么我们总共的子矩阵个数即为：

$$ \begin {aligned} & \sum _ {x _ 2 = 1} ^ N \sum _ {y _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} \sum _ {y _ 1 = 1} ^ {y _ 2} 1 \\\ = & \sum _ {x _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} \sum _ {y _ 2 = 1} ^ N \sum _ {y _ 1 = 1} ^ {y _ 2} 1 \\\ = & (\sum _ {x _ 2 = 1} ^ N \sum _ {x _ 1 = 1} ^ {x _ 2} 1) (\sum _ {y _ 2 = 1} ^ N \sum _ {y _ 1 = 1} ^ {y _ 2} 1) \\\ \end {aligned} $$

这两个式子是完全一样的，因此可化简为

$$ \begin {aligned} & (\sum _ {i = 1} ^ N \sum _ {j = 1} ^ i 1) ^ 2 \\\ = & (\sum _ {i = 1} ^ N i) ^ 2 \\\ = & (\frac {N (N + 1)} 2) ^ 2 \\\ \end {aligned} $$

那么我们就用大常数的线性做法解决了这题。

时间复杂度

$O(64n ^ 2) = O(n ^ 2)$。

C++ 代码（不卡常版，只过 $7$ 个点）

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;

int n;
int b[N][N];
bool a[N][N];

ll work()
{
    ll res = 0;
    static int stk[N], tt;
    static int f[N], l[N], g[N];
    memset(f, 0, sizeof f);
    for (int k = 1; k <= n; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            if (a[k][i]) f[i] ++ ;
            else    f[i] = 0;

        tt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            while (tt && f[stk[tt]] >= f[i]) tt -- ;
            l[i] = stk[tt];
            stk[ ++ tt] = i;
        }

        for (int i = 1; i <= n; i ++ )
        {
            g[i] = (f[i] * (i - l[i]) + g[l[i]]) % mod;
            (res += g[i]) %= mod;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", b[i] + j);

    ll res = 0;
    for (int k = 0; k < 31; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                a[i][j] = b[i][j] >> k & 1;
        (res += work() << k) %= mod;
    }
    printf("%lld ", res);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            b[i][j] ^= 0x7fffffff;

    res = 0;
    for (int k = 0; k < 31; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                a[i][j] = b[i][j] >> k & 1;
        (res += ((n * n * (n + 1ll) * (n + 1ll) / 4 - work()) % mod << k) % mod) %= mod;
    }
    printf("%lld\n", res);

    return 0;
}

关于卡常：

$a$ 不开了，直接在 work 中求第 $x$ 位。

$l$ 数组可以去掉，在处理单调栈时做 $\text{DP}$ 并计算答案。

读入数据量较多，scanf 改为快读。

将所有 i ++ 类自增运算改为 ++ i。

卡常后 C++ 代码（可 AC）

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;

int n;
int b[N][N];

inline int read()
{
    int x = 0; char c = getchar();
    while (~c && (c < 48 || c > 57)) c = getchar();
    for (; c > 47 && c < 58; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}

ll work(int x)
{
    ll res = 0;
    static int stk[N], tt;
    static int f[N], g[N];
    memset(f, 0, sizeof f);
    for (int k = 1; k <= n; ++ k)
    {
        for (int i = 1; i <= n; ++ i)
            if (b[k][i] >> x & 1) ++ f[i];
            else    f[i] = 0;

        tt = 0;
        for (int i = 1; i <= n; ++ i)
        {
            while (tt && f[stk[tt]] >= f[i]) -- tt;
            g[i] = f[i] * (i - stk[tt]) + g[stk[tt]];
            (res += g[i]) %= mod;
            stk[ ++ tt] = i;
        }
    }
    return res;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            b[i][j] = read();

    ll res = 0;
    for (int k = 0; k < 31; ++ k)
        (res += work(k) << k) %= mod;
    printf("%lld ", res);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            b[i][j] ^= 0x7fffffff;

    res = 0;
    for (int k = 0; k < 31; ++ k)
        (res += (n * n * (n + 1ll) * (n + 1ll) / 4 - work(k)) % mod << k) %= mod;
    printf("%lld\n", res);

    return 0;
}

$$ $$