勒庞"/>
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
更多推荐
9.9 勒庞
发布评论