[GXOI/GZOI2019]与或和

Posted on | In

一日双更休闲至极

考虑对矩阵中的数按二进制位计算贡献

对于$AND$运算，只有全$1$子矩阵有贡献

对于$OR$运算，只有全$0$子矩阵没有贡献

可以用单调栈做到$O(n^2)$计算贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a[1001][1001],b[1001][1001],u[1001][1001],high[1001],wide[1001];
inline long long clac (int n) {
	register long long sum=0,top=0,res=0;
	for(register int i=1;i<=n;++i) {
	    for(register int j=1;j<=n;++j) {
	    	u[i][j]=(b[i][j])?u[i-1][j]+1:0;
	    	register long long w=1,h=u[i][j];
	    	while(top&&h<=high[top])
			    sum-=high[top]*wide[top],w+=wide[top--];
			high[++top]=h,wide[top]=w;
			sum+=w*h; res+=sum;
		}
		sum=top=0;
	}
	return res%mod;
}
inline int read () {
	char ch=getchar(); register int num=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
	return num;
}
int main () {
	register int n=read(),m=(n+1)*n/2;
	for(register int i=1;i<=n;++i)
	    for(register int j=1;j<=n;++j) a[i][j]=read();
	register long long g=0,f=0,num=(long long)m*m%mod;
	for(register int k=0;k<32;++k) {
		for(register int i=1;i<=n;++i)
		    for(register int j=1;j<=n;++j) b[i][j]=(a[i][j]>>k)&1;
		(f+=clac(n)*(1<<k)%mod)%=mod;
		for(register int i=1;i<=n;++i)
		    for(register int j=1;j<=n;++j) b[i][j]^=1;
		(g+=(num-clac(n)+mod)*(1<<k)%mod)%=mod;
	}
	printf("%lld %lld\n",f,g);
	return 0;
}