题目
题解
化简问题后就成了对$01$矩阵求最大全$0/1$子矩阵
处理出来每个点往上最长延伸长度，然后单调栈解决即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=1e3+5,mod=1e9+7;
int n,ans,ans1,mx,Top;
int st[N];
int a[N][N],l[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]),mx=max(mx,a[i][j]);
for(int x=0,sum;(1ll<<x)<=mx;++x)
{
memset(l,0,sizeof(l));
sum=0;
for(int i=1;i<=n;++i,Top=0,sum=0)
for(int j=1;j<=n;++j)
{
if(a[i][j]&(1<<x)) l[i][j]=l[i-1][j]+1;
while(Top&&l[i][j]<=l[i][st[Top]]) (sum+=mod-1ll*(st[Top]-st[Top-1])*l[i][st[Top]]%mod)%=mod,--Top;
(sum+=1ll*(j-st[Top])*l[i][j]%mod)%=mod,st[++Top]=j,(ans+=1ll*sum*(1<<x)%mod)%=mod;
}
memset(l,0,sizeof(l));
for(int i=1;i<=n;++i,Top=0,sum=0)
for(int j=1;j<=n;++j)
{
(ans1+=1ll*i*j*(1<<x)%mod)%=mod;
if(!(a[i][j]&(1<<x))) l[i][j]=l[i-1][j]+1;
while(Top&&l[i][j]<=l[i][st[Top]]) (sum+=mod-1ll*(st[Top]-st[Top-1])*l[i][st[Top]]%mod)%=mod,--Top;
(sum+=1ll*(j-st[Top])*l[i][j]%mod)%=mod,st[++Top]=j,(ans1+=mod-1ll*sum*(1<<x)%mod)%=mod;
}
}
return printf("%d %d",ans,ans1),0;
}
