| 比赛 |
2026.4.11 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
与或和 |
最终得分 |
100 |
| 用户昵称 |
Ruyi |
运行时间 |
6.573 s |
| 代码语言 |
C++ |
内存使用 |
22.56 MiB |
| 提交时间 |
2026-04-11 11:17:24 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
#define N 1001
#define mod 1000000007
using namespace std;
ll n,a[N][N],tot,p2[35],ans1,ans2,cnt,h1[N][N],h2[N][N],st[N],top,lft[N],rgt[N];
ll calc(ll h[]){
ll res=0;
top=0;
for(int i=1;i<=n;i++){
while(top&&h[st[top]]>=h[i])top--;
lft[i]=top?st[top]:0;
st[++top]=i;
}
top=0;
for(int i=n;i>=1;i--){
while(top&&h[st[top]]>h[i])top--;
rgt[i]=top?st[top]:n+1;
st[++top]=i;
}
for(int i=1;i<=n;i++)res+=(ll)h[i]*(i-lft[i])*(rgt[i]-i);
return res;
}
int main(){
freopen("andorsum.in","r",stdin);
freopen("andorsum.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
p2[0]=1;
for(int i=1;i<32;i++) p2[i]=p2[i-1]*2%mod;
tot=(n*(n+1)/2)%mod;
tot=tot*tot%mod;
for(int i=0;i<31;i++){
memset(h1,0,sizeof(h1));
memset(h2,0,sizeof(h2));
cnt=0;
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(((a[j][k]>>i)&1)==1) h1[j][k]=h1[j-1][k]+1;
else h1[j][k]=0;
if(((a[j][k]>>i)&1)==0) h2[j][k]=h2[j-1][k]+1;
else h2[j][k]=0;
}
cnt+=calc(h1[j]);
}
ans1=(ans1+cnt%mod*p2[i])%mod;
cnt=0;
for(int j=1;j<=n;j++)cnt+=calc(h2[j]);
ans2=(ans2+(tot-cnt%mod+mod)%mod*p2[i])%mod;
}
cout<<ans1<<' '<<ans2<<endl;
return 0;
}