9.9 勒庞

勒庞"/>

9.9 勒庞

题意

给定一个\(n\times n\)的矩阵，定义矩阵的\(\tt{AND}\)值为矩阵中所有数与起来的运算结果；定义矩阵的\(\tt{OR}\)值为矩阵中所有数或起来的运算结果

试求出：

• 该矩阵所有子矩阵的\(\tt{AND}\)值之和
• 该矩阵所有子矩阵的\(\tt{OR}\)值之和

解法

这题全场\(A\)穿，然而我没想出来

与运算和或运算在每一位上是独立的，考虑按位计算

先考虑与运算，在按位分解后，问题就转化为了求一个矩阵中，有多少个全\(1\)子矩阵（全\(1\)子矩阵与起来才一定为\(1\)对答案产生\(1<<i\)的贡献）

可以考虑用单调栈\(O(n^2)\)解决这个问题

预处理出每个点向上能扩展的全\(1\)段的长度，维护一个单调递增的栈

枚举每一行，若当前行为第\(i\)行，记\(sum[j]\)为以第\(i\)行第\(j\)列为右下角的全\(1\)矩阵个数

单调栈维护\(sum\)即可（具体思路看代码，还是比较好懂的）

至于或运算，我们要求的就是含\(1\)子矩阵的个数

补集转化一下，用所有子矩阵的个数减去全\(0\)子矩阵的个数即是或运算的答案

代码

#include <cstdio>
#include <cstring>using namespace std;const int N = 2010;
const int mod = 998244353;int n, tot;
int a[N][N], tr[N][N], up[N][N];int top;
int st[N];long long sum[N];long long solve() {for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)    up[i][j] = 0;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (tr[i][j])    up[i][j] = up[i - 1][j] + tr[i][j];long long res = 0;for (int i = 1; i <= n; ++i) {top = 0;for (int j = 1; j <= n; ++j) {if (up[i][j] > up[i][st[top]])          //如果当前元素大于栈顶元素，直接加入栈，sum数组由栈顶转移 sum[j] = sum[st[top]] + up[i][j], st[++top] = j;else {                                  //否则一直弹出栈顶元素，维护新的sumwhile (up[i][j] <= up[i][st[top]] && top > 0) --top;sum[j] = (j - st[top]) * up[i][j] + sum[st[top]], st[++top] = j;}res = (res + sum[j]) % mod;}for (int j = 1; j <= n; ++j)    sum[j] = 0;    }return res;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)    scanf("%d", &a[i][j]);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)    tot = (tot + i * j) % mod;long long ans = 0;for (int i = 0; i < 31; ++i) {for (int j = 1; j <= n; ++j)for (int k = 1; k <= n; ++k)    tr[j][k] = (a[j][k] >> i) & 1;ans = (ans + solve() * (1 << i) % mod) % mod;}printf("%lld\n", ans);ans = 0;for (int i = 0; i < 31; ++i) {for (int j = 1; j <= n; ++j)for (int k = 1; k <= n; ++k)    tr[j][k] = (a[j][k] >> i) & 1 ^ 1;ans = (ans + (tot - solve()) * (1 << i) % mod + mod) % mod;}printf("%lld\n", ans);return 0;
}

转载于:.html