Luogu

BZOJ

LOJ

分析

依次考虑每一位。

对于 $\texttt{AND}$ ,显然只有全 $1$ 矩阵才有贡献;对于 $\texttt{OR}$ ,显然只有全 $0$ 矩阵才没有贡献。

那么利用单调栈求出所有的全 $1$ 和全 $0$ 矩阵即可。

至于具体怎么求:假设要求全 $1$ 矩阵,那么先求出每个元素往上能扩展的 $1$ 的个数,然后对于每一行扫一遍,拿单调栈维护一下就可以求出以每个元素为右下角的全 $1$ 矩阵个数了。

时间复杂度 $O(n^2\log \mathrm{SIZE})$ , 这里的 $\mathrm{SIZE}$ 是值域。然而不知道为什么在 $\mathrm{BZOJ}$ 上 $\mathrm{T}$ 了。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1000000007;
const int N=1000+10;

int n;
int a[N][N],b[N][N],s[N][N];
int sta[N],top=0;

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            a[i][j]=read();
    int andsum=0,orsum=0;
    for (re int bit=0;bit<31;++bit) {
        int bitsum=(1<<bit)%mod;
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                b[i][j]=(a[i][j]>>bit)&1;
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j) {
                if (!b[i][j]) s[i][j]=0;
                else s[i][j]=s[i-1][j]+1;
            }
        for (re int i=1;i<=n;++i) {
            top=0,sta[top]=0; int now=0;
            for (re int j=1;j<=n;++j) {
                while (top&&s[i][sta[top]]>=s[i][j])
                    now=(now-1ll*(sta[top]-sta[top-1])*s[i][sta[top]]%mod+mod)%mod,--top;
                now=(now+1ll*(j-sta[top])*s[i][j]%mod)%mod,sta[++top]=j;
                andsum=(andsum+1ll*now*bitsum%mod)%mod;
            }
        }
        
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j)
                b[i][j]^=1;
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j) {
                if (!b[i][j]) s[i][j]=0;
                else s[i][j]=s[i-1][j]+1;
            }
        orsum=(orsum+1ll*bitsum*(1ll*n*(n+1)/2*n*(n+1)/2%mod)%mod)%mod;
        for (re int i=1;i<=n;++i) {
            top=0,sta[top]=0; int now=0;
            for (re int j=1;j<=n;++j) {
                while (top&&s[i][sta[top]]>=s[i][j])
                    now=(now-1ll*(sta[top]-sta[top-1])*s[i][sta[top]]%mod+mod)%mod,--top;
                now=(now+1ll*(j-sta[top])*s[i][j]%mod)%mod,sta[++top]=j;
                orsum=(orsum-1ll*now*bitsum%mod+mod)%mod;
            }
        }
    }
    printf("%d %d\n",andsum,orsum);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 19 PM