#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
ll n,a[1005][1005],s[1005][1005];
const ll mod=1e9+7;
int st[2005],top;
inline int getdigand(int digit){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(((a[i][j]>>digit)&1)) s[i][j]=s[i-1][j]+1;
			else s[i][j]=0;
		}
	}
	ll ans=0,ans2=0;
	for(int i=1; i<=n; i++){
		top=0;
		ans=0;
		for(int j=1; j<=n; j++){
			ans+=s[i][j];
			while(top&&s[i][st[top]]>=s[i][j]){
				ans-=(st[top]-st[top-1])*(s[i][st[top]]-s[i][j]);
				top--;
			}
			(ans2+=ans)%=mod; 
			ans%=mod;
			st[++top]=j;
		}
	} 
	return ans2%mod;
}
inline int getdigor(int digit){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(((a[i][j]>>digit)&1)) s[i][j]=0;
			else s[i][j]=s[i-1][j]+1;
		}
	}
	ll ans=0,ans2=0;
	for(int i=1; i<=n; i++){
		top=0;
		ans=0;
		for(int j=1; j<=n; j++){
			ans+=s[i][j];
			while(top&&s[i][st[top]]>=s[i][j]){
				ans-=(st[top]-st[top-1])*(s[i][st[top]]-s[i][j]);
				top--;
			}
			(ans2+=(i*j-ans))%=mod;
			ans%=mod;
			st[++top]=j;
		}
	} 
	return ans2%mod;
}
int getand(){
	int ans=0;
	for(int i=30; i>=0; i--){
		ans+=getdigand(i)*(1ll<<i)%mod;
		ans%=mod;
	}
	return ans;
}
int getor(){
	int ans=0;
	for(int i=30; i>=0; i--){
		ans+=getdigor(i)*(1ll<<i)%mod;
		ans%=mod;
	}
	return ans;
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	cin>>n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin>>a[i][j];
		}
	}
	cout<<getand()<<" "<<getor()<<"\n";
	return 0;
}

0 条评论

目前还没有评论...

信息

ID
840
时间
1000ms
内存
256MiB
难度
9
标签
(无)
递交数
59
已通过
4
上传者