比赛 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;
}