题目分析

我们需要计算所有子矩阵的 AND 值之和与 OR 值之和。

直接枚举所有子矩阵的复杂度是 $O(n^4)$，对于 $n \leq 1000$ 来说不可行。

解题思路

核心思想：按位独立计算

利用位运算的性质，我们可以对每个二进制位独立计算：

• AND 和：对于第 $k$ 位，只有当子矩阵中所有数字的第 $k$ 位都是 1 时，该子矩阵的 AND 值在第 $k$ 位才为 1
• OR 和：对于第 $k$ 位，只要子矩阵中至少有一个数字的第 $k$ 位是 1，该子矩阵的 OR 值在第 $k$ 位就为 1

问题转化

对于每个二进制位 $k$：

1. AND 问题：转化为统计全 1 子矩阵的数量
2. OR 问题：转化为统计至少包含一个 1 的子矩阵数量 = 总子矩阵数 - 全 0 子矩阵数

高效算法

使用单调栈来高效统计全 1 子矩阵的数量：

• 对于每一列，计算以该位置为底边的最大连续 1 的高度
• 使用单调栈在 $O(n)$ 时间内计算以每一行为底边的全 1 子矩阵数量
• 总复杂度：$O(n^2 \times \text{位数})$

代码实现

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MOD = 1000000007;

// 计算所有子矩阵的AND值之和
long long solveAND(vector<vector<int>>& matrix, int n) {
    long long total = 0;
    
    // 对每个位独立计算
    for (int bit = 0; bit < 31; bit++) {
        vector<vector<int>> height(n, vector<int>(n, 0));
        
        // 计算每个位置向上的连续1的个数（在当前bit位）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((matrix[i][j] >> bit) & 1) {
                    height[i][j] = (i == 0) ? 1 : height[i-1][j] + 1;
                } else {
                    height[i][j] = 0;
                }
            }
        }
        
        // 对每一行使用单调栈计算全1子矩阵数量
        for (int i = 0; i < n; i++) {
            stack<int> st;
            vector<int> left(n, 0), right(n, n);
            
            // 计算左边第一个小于当前高度的位置
            for (int j = 0; j < n; j++) {
                while (!st.empty() && height[i][st.top()] >= height[i][j]) {
                    st.pop();
                }
                left[j] = st.empty() ? -1 : st.top();
                st.push(j);
            }
            
            // 清空栈
            while (!st.empty()) st.pop();
            
            // 计算右边第一个小于当前高度的位置
            for (int j = n-1; j >= 0; j--) {
                while (!st.empty() && height[i][st.top()] > height[i][j]) {
                    st.pop();
                }
                right[j] = st.empty() ? n : st.top();
                st.push(j);
            }
            
            // 计算以当前行为底边的全1子矩阵数量
            for (int j = 0; j < n; j++) {
                if (height[i][j] > 0) {
                    long long count = (long long)height[i][j] * (j - left[j]) * (right[j] - j);
                    total = (total + (count % MOD) * (1LL << bit)) % MOD;
                }
            }
        }
    }
    
    return total;
}

// 计算所有子矩阵的OR值之和
long long solveOR(vector<vector<int>>& matrix, int n) {
    long long total = 0;
    long long totalSubmatrices = (long long)n * n * (n + 1) * (n + 1) / 4; // 总子矩阵数
    
    // 对每个位独立计算
    for (int bit = 0; bit < 31; bit++) {
        vector<vector<int>> height(n, vector<int>(n, 0));
        
        // 计算每个位置向上的连续0的个数（在当前bit位）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!((matrix[i][j] >> bit) & 1)) {
                    height[i][j] = (i == 0) ? 1 : height[i-1][j] + 1;
                } else {
                    height[i][j] = 0;
                }
            }
        }
        
        long long zeroCount = 0;
        
        // 对每一行使用单调栈计算全0子矩阵数量
        for (int i = 0; i < n; i++) {
            stack<int> st;
            vector<int> left(n, 0), right(n, n);
            
            // 计算左边第一个小于当前高度的位置
            for (int j = 0; j < n; j++) {
                while (!st.empty() && height[i][st.top()] >= height[i][j]) {
                    st.pop();
                }
                left[j] = st.empty() ? -1 : st.top();
                st.push(j);
            }
            
            // 清空栈
            while (!st.empty()) st.pop();
            
            // 计算右边第一个小于当前高度的位置
            for (int j = n-1; j >= 0; j--) {
                while (!st.empty() && height[i][st.top()] > height[i][j]) {
                    st.pop();
                }
                right[j] = st.empty() ? n : st.top();
                st.push(j);
            }
            
            // 计算以当前行为底边的全0子矩阵数量
            for (int j = 0; j < n; j++) {
                if (height[i][j] > 0) {
                    long long count = (long long)height[i][j] * (j - left[j]) * (right[j] - j);
                    zeroCount = (zeroCount + count) % MOD;
                }
            }
        }
        
        // 当前位为1的子矩阵数量 = 总子矩阵数 - 全0子矩阵数
        long long oneCount = (totalSubmatrices - zeroCount + MOD) % MOD;
        total = (total + oneCount * (1LL << bit)) % MOD;
    }
    
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    long long andSum = solveAND(matrix, n);
    long long orSum = solveOR(matrix, n);
    
    cout << andSum << " " << orSum << endl;
    
    return 0;
}

算法复杂度

• 时间复杂度：$O(31 \times n^2)$，其中 31 是位数（因为数字最大到 $2^{31}-1$）
• 空间复杂度：$O(n^2)$

关键点说明

1. 单调栈技巧：用于高效计算以每个位置为高度的矩形面积
2. 位独立计算：将复杂的位运算问题分解为独立的二进制位问题
3. 容斥原理：OR 问题通过 "总数 - 全0数" 来计算

这种方法能够高效处理 $n = 1000$ 的大数据规模，是解决此类位运算矩阵问题的标准方法。