- 矩阵(matrix)文件读写
TLE qwq
- @ 2026-9-9 10:43:24
#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
- 上传者