QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #422021 | #2972. 与或和 | rzh123 | 100 ✓ | 925ms | 12968kb | C++23 | 1.3kb | 2024-05-26 16:40:03 | 2024-05-26 16:40:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1005,P=1e9+7,I2=5e8+4;
int n,a[N][N],tot;
bool b[N][N];
int calc(int _){
// 统计全 0/1 子矩阵数量
static int h[N][N];
int ret{0};
for(int i{1};i<=n;++i){
stack<pair<int,int> > stk;
stk.emplace(0,0);
for(int j{1};j<=n+1;++j){
if(j<=n&&b[i][j]==_) h[i][j]=h[i-1][j]+1;
else h[i][j]=0;
int w{0};
while(stk.size()>1u&&stk.top().first>=h[i][j]){
auto t=stk.top(); stk.pop();
w+=t.second;
int x=1ll*w*(w+1)/2ll%P*(t.first-max(h[i][j],stk.top().first))%P;
// printf("i=%d,j=%d,w=%d,x=%d\n",i,j,w,x);
ret=(ret+x)%P;
}
stk.emplace(h[i][j],w+1);
}
}
// printf("calc %d = %d\n",_,ret);
return ret;
}
inline void consb(int msk){
// printf("consb %d\n",msk);
for(int i{1};i<=n;++i)
for(int j{1};j<=n;++j)
b[i][j]=(a[i][j]&msk);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i{1};i<=n;++i)
for(int j{1};j<=n;++j)
cin>>a[i][j];
for(int i{1};i<=n;++i)
for(int j{1};j<=n;++j)
tot=(tot+1ll*i*j)%P;
int ans1{0},ans2{0};
for(int i{0};i<31;++i){
int v=(1<<i)%P;
consb(1<<i);
ans1=(ans1+1ll*calc(1)*v)%P;
ans2=(ans2+1ll*(tot-calc(0)+P)%P*v)%P;
}
printf("%d %d\n",ans1,ans2);
return 0;
}// 对拍过
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 7952kb
input:
10 74 48 33 5 83 28 1 98 45 65 63 19 29 12 72 48 25 70 60 21 69 97 37 96 100 11 38 81 29 45 17 67 44 61 90 74 51 41 16 59 23 21 85 76 55 32 53 49 93 24 29 2 58 89 13 43 21 67 13 48 20 63 78 99 13 94 48 51 37 54 60 84 22 37 28 74 5 72 7 63 96 86 33 52 0 95 92 95 78 55 3 94 37 10 65 3 23 95 15 55
output:
11362 356443
result:
ok single line: '11362 356443'
Test #2:
score: 10
Accepted
time: 1ms
memory: 7856kb
input:
10 4 93 7 72 10 91 63 48 26 34 22 17 68 16 1 58 15 55 73 86 51 53 2 86 89 32 29 70 83 33 69 8 41 14 34 31 51 27 59 36 44 5 40 60 84 96 18 73 30 57 16 89 50 7 25 53 7 49 75 65 1 92 58 40 0 5 29 13 93 38 89 64 6 25 2 68 87 65 40 67 32 90 32 39 64 42 56 20 47 26 18 31 30 1 100 56 23 92 92 1
output:
8220 350244
result:
ok single line: '8220 350244'
Test #3:
score: 10
Accepted
time: 3ms
memory: 9984kb
input:
50 79 83 82 13 8 34 63 5 43 61 99 83 71 87 16 33 6 3 72 93 27 89 80 81 2 66 32 34 12 90 9 23 33 39 44 90 82 2 96 22 56 3 48 86 32 56 81 78 15 18 93 45 60 8 77 22 91 69 91 81 48 86 2 87 90 85 1 63 32 25 8 21 37 39 60 33 80 14 85 77 50 10 96 21 61 62 20 72 72 68 39 45 63 96 72 81 94 98 93 87 64 99 15 ...
output:
308684 205557486
result:
ok single line: '308684 205557486'
Test #4:
score: 10
Accepted
time: 8ms
memory: 10228kb
input:
100 100 17 59 80 34 91 12 22 15 69 11 100 89 49 15 22 74 20 18 31 81 48 77 46 69 28 90 90 74 77 53 57 64 42 72 2 89 11 92 6 2 80 23 19 44 88 88 45 84 17 89 42 39 79 41 2 78 62 78 6 60 59 37 92 16 37 29 88 84 96 89 28 38 10 21 45 5 84 50 46 7 68 86 100 74 81 88 91 49 38 73 29 29 61 26 79 63 9 100 94 ...
output:
1209195 235259371
result:
ok single line: '1209195 235259371'
Test #5:
score: 10
Accepted
time: 7ms
memory: 6284kb
input:
100 24 31 24 88 46 11 59 54 20 83 76 29 86 43 90 83 79 95 54 21 64 2 86 11 64 64 7 50 50 18 33 56 46 75 1 10 69 58 37 47 69 3 43 87 6 80 30 6 33 49 23 40 59 53 98 55 18 6 91 4 60 19 29 82 18 71 64 82 98 60 39 100 54 49 57 16 16 99 16 96 65 17 2 57 51 100 11 60 2 94 36 55 24 49 43 88 37 85 36 48 24 8...
output:
1221832 235280845
result:
ok single line: '1221832 235280845'
Test #6:
score: 10
Accepted
time: 232ms
memory: 11248kb
input:
500 960722370 1959072451 990684643 1912670706 1811833843 1764772908 1995065130 178399534 878154562 217514796 1307871539 1461876200 1697426127 1057977542 76048120 324490063 779955831 324435007 958317082 1917357211 310784947 2121194939 694410299 889529464 30571844 1343780363 1834705222 1613724048 7499...
output:
705640719 12674015
result:
ok single line: '705640719 12674015'
Test #7:
score: 10
Accepted
time: 925ms
memory: 12708kb
input:
1000 2093093615 926680383 444208321 2118256449 845365680 1908703754 3033244 1373933942 1846800199 1695838041 1133232003 626074155 27844231 1471029241 1462524427 1791984149 1413626989 899577385 1300255483 913270227 1980690670 1184094700 450493620 1821997939 17232734 174315142 1284146637 1029513702 20...
output:
886343551 711904422
result:
ok single line: '886343551 711904422'
Test #8:
score: 10
Accepted
time: 917ms
memory: 12552kb
input:
1000 1545645860 232607795 558606626 1015202650 1372818610 2105867857 909582806 1794136305 781452477 651311305 1459928581 145338251 1118861564 1521979914 1237144060 1637153882 1942071831 1332651841 340799734 1773044172 1356013281 1134153785 281185264 940033240 173535408 204297961 537226821 1713156086...
output:
859637311 37305124
result:
ok single line: '859637311 37305124'
Test #9:
score: 10
Accepted
time: 913ms
memory: 12968kb
input:
1000 40297396 1262749490 1975677632 777972346 1727210233 314663919 723840091 1640624126 2102226278 1098970572 329775220 1070525877 540827818 512953540 66491294 1899497623 1651202416 1411737525 253115615 107105791 1784157120 369798781 64989666 1868886422 323507628 2027918024 1279151617 798321335 4109...
output:
111354892 517544957
result:
ok single line: '111354892 517544957'
Test #10:
score: 10
Accepted
time: 915ms
memory: 12676kb
input:
1000 507560597 804265326 1848905248 109573199 771903824 1526478388 2001424072 332133876 1950402796 1433520011 1190176166 765449598 785896649 267760135 1780558726 529715335 202611116 315758344 763503324 2134902309 1877295469 1907294399 65422481 1509552392 1203761084 116904094 347211810 1142504372 946...
output:
780857261 569016480
result:
ok single line: '780857261 569016480'