洛谷P5300 [GXOI/GZOI2019] 与或和题解

题目链接：P5300 [GXOI/GZOI2019] 与或和

题意：

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

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

给定一个 \(N \times N\) 的矩阵，她希望求出： 1. 该矩阵的所有子矩阵的 \(\texttt{AND}\) 值之和（所有子矩阵 \(\texttt{AND}\) 值相加的结果）。 2. 该矩阵的所有子矩阵的 \(\texttt{OR}\) 值之和（所有子矩阵 \(\texttt{OR}\) 值相加的结果）。

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

由于答案可能非常的大，你只需要输出答案对 \(1,000,000,007 (10^9 + 7)\) 取模后的结果。

输入格式：

输入文件的第一行是一个正整数 \(N\)，表示矩阵的尺寸。

接下来 \(N\) 行，每行 \(N\) 个自然数，代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。

输出格式：

输出只有一行，包含两个用空格隔开的整数，第一个应为所有子矩阵 \(\texttt{AND}\) 值之和除以 \(10^9 + 7\) 的余数，第二个应为所有子矩阵 \(\texttt{OR}\) 值之和除以 \(10^9 + 7\) 的余数。

数据范围：

\(1 \le n \le 10^3,~0 \le a_{ij} \le 2^{31}-1\) 。

讲一个不同单调栈或单调队列的做法。

因为 \((1\land 1)=1\) 以及 \((0\lor 0)=0\) ，所以我们把每个数取反就可以把 \(\rm AND\) 操作转成 \(\rm OR\) 操作的计算了。

考虑枚举每一个二进制位，我们要求出这一位 \(\rm OR\) 和为 \(1\) 的子矩阵的个数。

枚举矩阵的右下角 \((i,j)\) 。记 \(s_i\) 为到当前行 \(i\) 为止，当前位为 \(1\) 的数最后出现的行

显然以 \((i,j)\) 为右下角的合法矩阵的数量相当于对每一列以 \(j\) 为右端点作后缀最大值再加起来的结果

由于后缀最大值是单调的，且每次只会修改单个点 \((i,j)\) ，因此考虑记 \(r_i\) 为 \(i\) 左侧第一个比它大的

那么后缀最大值的和就可以用 \(r_i\) 计算出来。具体见代码。

时间复杂度 \(\mathcal{O}(n^2 \log V)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e3 + 15))

const int mx = (1ll << 31) - 1;
int n, s[N], r[N], v[N], a[N][N];
int solve(int k)
{
    int res = 0; rep(i, 1, n) s[i] = r[i] = 0;
    rep(i, 1, n)
    {
        for(int j = 1, w = 0; j <= n; j++)
        {
            if((a[i][j] >> k) & 1) { s[j] = i, r[w = j] = 0; }
            else if(w > r[j]) r[j] = w;
            v[j] = v[r[j]] + s[j] * (j - r[j]); add(res, v[j] % mod);
        }
    }
    return res * (1ll << k) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
    int ans1 = 0, ans2 = 0;
    rep(i, 0, 30) add(ans2, solve(i));
    rep(i, 1, n) rep(j, 1, n) {
        a[i][j] ^= mx; add(ans1, i * j % mod * mx % mod);
    } rep(i, 0, 30) add(ans1, mod - solve(i));
    cout << ans1 << ' ' << ans2 << '\n';
    return 0;
}