洛谷 P5300 分析（别看）

科技起源的小号1

2026-08-28 15:07:17

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：两个具体值

1.2 题目背景、允许、禁止与限制

背景：
有一个 $N\times N$ 的矩阵
允许：
求出所有子矩阵的 & 和以及 | 和

1.3 题目数据范围与猜测

$2 \le n \le 1000 \longrightarrow O(n^2)$
$矩阵中的数字 \le 2^{31} - 1$

1.4 一句话概括题意

求出所有子矩阵的二进制 & 和以及 | 值之和

2 题目破题推导

2.1 第一步：大拆小，小组大

我们先思考一种最简单的情况：矩阵全为0/1
这样 & 和本质上就是求矩阵中全为 $1$ 的子矩阵的和
这样 | 和本质上就是求矩阵中不全为 $0$ 的子矩阵的和
这样其实很理想化，所以我们可以尝试将大问题转化为上述问题
怎么办呢？题目中给出了叫做“二进制”，这不就是一个性质吗？我们可以进行二进制拆分，对于每一位计算
然后最终每次加上的就是 $当前的答案 \times 2^{k(当前是第几位)}$

2.2 第二步：分情况讨论

现在只考虑求全为1矩阵个数的情况即可！因为0同理
记 $up[i]$ 为当前这一行第 $i$ 列往上连续1的个数

第一种情况：前面和后面一样高
那直接加入本次的 $up[i]$ 即可
为什么？因为我们想象一下原来答案为 $3$ ， $up[1]=3,up[2]=3$ ，那么加入第二行的时候，个数其实就是 $up[1]+up[2]=6$
第二种情况：前面低，后面高
依旧直接加入本次的 $up[i]$ 即可
为什么？因为我们想象一下原来答案为 $3$ ， $up[1]=3,up[2]=4$ ，那么加入第二行的时候，个数其实就是 $up[1]+up[2]=7$
第三种情况：前面高，后面低
这就和前面两种不同了！
如果还是累加 $up[i]$ ，会发现这一列上方的空白区域却和前面 $1$ 的组成一个矩阵（相当于连不上）
所以我们本质上要记录一个对于这一列需要删除的高度
维护一个单调递增栈，加入一项后若不再满足单调性，则将整体答案减去要删去的那部分
这部分的大小即为： $(当时栈顶高度-当前加入高度) \times 栈顶与次栈顶的距离$
为什么不是直接减去 $(当时栈顶高度-当前加入高度) \times 1$ ，而是要栈顶与次栈顶的距离呢？
举个例子：

 1
 1
 1
11
11
首先加入
1
1
1
1
的时候，会消去 (5-4) * (5-4)=1的1
再来，加入
1
1
1
的时候，会消去 (4-3) * (5-3)=2的1
发现了吗
高度为5的那列1在高度为4入队的时候只消去了1格，但是在高度为3入队的时候又该消去一格，然后
还需要消去高度为4对应的那一格，因此这就是不能使用(当时栈顶高度-当前加入高度) * 1

3 模型匹配

维护一个单调递增栈->单调栈

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
const int N = 1111;
const int MOD = 1e9 + 7;
int a[N][N];
int up[N][N];

signed main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int k = 0;k <= 31;k++){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= n;j++){
                if ((a[i][j] >> k) & 1){
                    up[i][j] = up[i - 1][j] + 1;
                } else {
                    up[i][j] = 0;
                }
            }
        }
        for (int i = 1;i <= n;i++){
            int temp = 0;
            stack<int> s;
            for (int j = 1;j <= n;j++){
                temp += up[i][j];
                while(!s.empty() && up[i][j] < up[i][s.top()]){
                    int tttt = s.top();
                    s.pop();
                    int ttt = (!s.empty()? s.top() : 0);
                    s.push(tttt);
                    temp -= (tttt - ttt) * (up[i][s.top()] - up[i][j]);
                    s.pop();
                }
                ans += temp << k;
                ans %= MOD;
                s.push(j);
            }
        }
    }
    cout << ans << " ";
    ans = 0;
    for (int k = 0;k <= 31;k++){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= n;j++){
                if (!((a[i][j] >> k) & 1)){
                    up[i][j] = up[i - 1][j] + 1;
                } else {
                    up[i][j] = 0;
                }
            }
        }
        for (int i = 1;i <= n;i++){
            int temp = 0;
            stack<int> s;
            for (int j = 1;j <= n;j++){
                temp += up[i][j];
                while(!s.empty() && up[i][j] < up[i][s.top()]){
                    int tttt = s.top();
                    s.pop();
                    int ttt = (!s.empty()? s.top() : 0);
                    s.push(tttt);
                    temp -= (tttt - ttt) * (up[i][s.top()] - up[i][j]);
                    s.pop();
                }
                ans += (i * j - temp) << k;
                ans %= MOD;
                s.push(j);
            }
        }
    }
    cout << ans << " ";
    
    return 0;
}