update on 26.9.16:

我图好像炸了，但是我懒得搞了，各位尽量发挥想象能力。

SOLUTION

首先容易想到要拆位，对于每一位做一遍，然后带权加起来。

现在问题转化为在 $01$ 矩阵上求这个东西。

我们枚举子矩阵的右下点，统计他左上可以贡献的点数。

首先对于子矩阵与的和，看看这个丑陋的图：

这是当前点左上的子矩阵。

假如说红色代表 $1$，那么我们可以发现，可能产生贡献的左上角是下面这些蓝色的：

可以发现，这是一个楼梯形状的东西，也就是说，每一行蓝色的长度在向下扩展的时候不减。

于是我们可以很轻松地处理出每一个点左边第一个 $0$，然后按先列后行的顺序枚举，用单调栈维护蓝色范围的面积，这个具体看代码实现，在此不做过多赘述。

然后他对答案的贡献就是这个蓝色的面积大小再乘上一个当前二进制位的权值，所以我们把这一部分搞定了。

对于子矩阵或的和，我们不妨做一个容斥，将其变成所有的点减去不能产生贡献的点，然后算答案。

方法与上文所述基本相同，相当于把 $0$ 看作 $1$，$1$ 看作 $0$，读者可以自己思考。

然后我们就搞定了这道题，写完小清新代码，交上去一看：

TLE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int mat[1010][1010],mt[1010][1010],pre0[1010][1010],pre1[1010][1010];
pair<int,int> stk[1010];
const int mod=1e9+7;
signed main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            cin>>mat[i][j];
        }
    }
    int sum_and=0,sum_or=0;
    for(register int s=0;s<=30;s++){
        for(register int i=1;i<=n;i++){
            for(register int j=1;j<=n;j++){
                mt[i][j]=((mat[i][j]>>s)&1);
                if(mt[i][j]==1) pre1[i][j]=j;
                else pre1[i][j]=pre1[i][j-1];
                if(mt[i][j]==0) pre0[i][j]=j;
                else pre0[i][j]=pre0[i][j-1];
            }
        }
        for(register int j=1;j<=n;j++){
            int top=0,sum=0;
            for(register int i=1;i<=n;i++){
                pair<int,int> p={j-pre0[i][j],1};
                while(top&&stk[top].fi>=p.fi){
                    sum-=stk[top].fi*stk[top].se;
                    p.se+=stk[top--].se;
                }
                stk[++top]=p,sum+=p.fi*p.se;
                sum_and=(sum_and+(1<<s)%mod*sum%mod)%mod;
            }
        }
        for(register int j=1;j<=n;j++){
            int top=0,sum=0;
            for(register int i=1;i<=n;i++){
                pair<int,int> p={j-pre1[i][j],1};
                while(top&&stk[top].fi>=p.fi){
                    sum-=stk[top].fi*stk[top].se;
                    p.se+=stk[top--].se;
                }
                stk[++top]=p,sum+=p.fi*p.se;
                sum_or=(sum_or+(1<<s)%mod*(i*j-sum)%mod)%mod;
            }
        }
    }
    cout<<sum_and<<' '<<sum_or<<'\n';
    return 0;
}

不不不，我无疑是愤怒的，为啥我的 $n^2 \log V$ 代码跑的还不如隔壁 yangjunlin3399 dalao 的 $n^3 \log V$ 代码跑得快？

然后发现这个题需要卡常。

大概的方法差不多是合并循环，不用 #define int 龙龙，使用一些 register 等。

于是我们艰难地卡过了，你可以发现我有 $4$ 个点是卡着时限过的。

RECORD

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int T,n,m;
int mat[1010][1010],pre0[1010][1010],pre1[1010][1010];
pair<int,int> stk[1010],stk1[1010];
const int mod=1e9+7;
signed main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            cin>>mat[i][j];
        }
    }
    ll sum_and=0,sum_or=0;
    for(register int s=0;s<=30;s++){
		int x;
        for(register int i=1;i<=n;i++){
            for(register int j=1;j<=n;j++){
				x=(mat[i][j]>>s)&1;
                if(x) pre1[i][j]=j,pre0[i][j]=pre0[i][j-1];
                else pre1[i][j]=pre1[i][j-1],pre0[i][j]=j;
            }
        }
        for(register int j=1;j<=n;j++){
            int top=0,top1=0;
			ll sum=0,sum1=0;
            for(register int i=1;i<=n;i++){
                pair<int,int> p={j-pre0[i][j],1};
                while(top&&stk[top].fi>=p.fi){
                    sum-=stk[top].fi*stk[top].se;
                    p.se+=stk[top--].se;
                }
                stk[++top]=p,sum+=p.fi*p.se;
                sum_and=(sum_and+(ll)(1<<s)*sum)%mod;
				
                pair<int,int> p1={j-pre1[i][j],1};
                while(top1&&stk1[top1].fi>=p1.fi){
                    sum1-=stk1[top1].fi*stk1[top1].se;
                    p1.se+=stk1[top1--].se;
                }
                stk1[++top1]=p1,sum1+=p1.fi*p1.se;
                sum_or=(sum_or+(ll)(1<<s)*(i*j-sum1))%mod;
            }
        }
    }
    cout<<sum_and<<' '<<sum_or<<'\n';
    return 0;
}