【题解】Luogu P5300 [GXOI/GZOI2019]与或和

原题传送门

我们珂以拆位，拆成一个个0/1矩阵

贡献珂以用全0，全1的子矩阵的个数来计算

全0，全1的子矩阵的个数珂以用悬线法/单调栈解决

#include <bits/stdc++.h>

#define N 1005

#define mod 1000000007

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

int n,a[N][N],len[N],all,ans1,ans2;

pair<int,int>s[N];

inline int work(register int t,register int opt)

{

	int res=0;

	for(register int i=1;i<=n;++i)

		len[i]=0;

	for(register int i=1;i<=n;++i)

	{

		int top=0,sum=0;

		for(register int j=1;j<=n;++j)

		{

			len[j]=(a[i][j]>>t&1)==opt?len[j]+1:0;

			int tmp=1;

			while(top&&s[top].first>=len[j])

				sum-=s[top].first*s[top].second,tmp+=s[top--].second;

			sum+=len[j]*tmp;

			res=(res+sum)%mod;

			s[++top]=make_pair(len[j],tmp);

		}

	}

	return res;

}

int main()

{

	n=read();

	for(register int i=1;i<=n;++i)

		for(register int j=1;j<=n;++j)

			a[i][j]=read(),all=(all+i*j)%mod;

	for(register int i=0,j=1;i<31;++i,j<<=1)

	{

		ans1=(ans1+1ll*work(i,1)*j)%mod;

		ans2=(ans2+1ll*(all-work(i,0)+mod)*j)%mod;

	}

	write(ans1),putchar(' '),write(ans2);

	return 0;

}