题目大意:
1. 求所有的子矩阵的and之和
2. 求所有子矩阵的or之和由于是位运算,那么久直接拆位,于是就变成了求全0子矩阵的个数和全1子矩阵的个数
那么题目就变成了简单的单调栈问题
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; #define re register #define ll long long #define gc getchar() inline int read() { re int x(0),f(1);re char c(gc); while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc; while(c>='0'&&c<='9')x=x*10+c-48,c=gc; return f*x; } const int N=1010,mod=1e9+7; int n,a[N][N],h[N][N],top,s[N]; ll ans; int main() { n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=read(); 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) h[i][j]=h[i-1][j]+1; else h[i][j]=0; } for(int i=1;i<=n;++i) { ll an(0);top=0; for(int j=1;j<=n;++j) { an+=h[i][j]; while(top&&h[i][s[top]]>=h[i][j]) an-=(s[top]-s[top-1])*(h[i][s[top--]]-h[i][j]); ans+=an<<k; ans%=mod; s[++top]=j; } } } cout<<ans<<" "; ans=0,top=0; memset(s,0,sizeof(s)); 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) h[i][j]=0; else h[i][j]=h[i-1][j]+1; } for(int i=1;i<=n;++i) { ll an(0);top=0; for(int j=1;j<=n;++j) { an+=h[i][j]; while(top&&h[i][s[top]]>=h[i][j]) an-=(s[top]-s[top-1])*(h[i][s[top--]]-h[i][j]); ans+=(1LL*i*j-an)<<k; ans%=mod; s[++top]=j; } } } cout<<ans<<" "; return 0; }