//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define endl '\n'
const int N=1010;
const ll mod=1000000007;
int S[7][7][N][N];
int a[N];
ll pw[N*N];
void solve(){
pw[0]=1ll;
for (int i=1;i<N*N;i++){
pw[i]=(pw[i-1]*2ll)%mod;
}
int n;cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
int q;cin>>q;
for (int i=1;i<=q;i++){
int l,r,x;cin>>l>>r>>x;
for (int j=0;j<7;j++){
for (int t=0;t<7;t++){
if ((x&(1<<j)) && (x&(1<<t))){
S[j][t][l][r]++;
}
}
}
}
for (int x=0;x<7;x++){
for (int y=0;y<7;y++){
for (int i=1;i<=n;++i){
for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i][j-1];
for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i-1][j];
}
}
}
ll res=0ll;
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++){
ll mult=i*(n-j+1);
if (i<j) mult*=2;
for (int x=0;x<7;x++){
for (int y=0;y<7;y++){
// 1<=l<=i
// i<=r<=n
int cnt=S[x][y][i][n]-S[x][y][0][j]-S[x][y][i][j-1]+S[x][y][0][j-1];
int cnt_x=S[x][x][i][n]-S[x][x][0][i-1]-S[x][x][i][i-1]+S[x][x][0][i-1];
int cnt_y=S[y][y][j][n]-S[y][y][0][j-1]-S[y][y][j][j-1]+S[y][y][0][j-1];
cnt_x-=cnt;
cnt_y-=cnt;
int SS=(cnt>0)+(cnt_x>0)+(cnt_y>0);
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
// if (i==1 && j==1 && x==0 && y==1){
// cout<<"OK "<<mult<<" "<<SS<<endl;
// }
if (SS>=2){
res+=pw[q-2+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x)) && (a[j]&(1<<y))){
// cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
// cout<<mult<<endl;
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x)) && (a[j]&(1<<y))==0 && cnt_y){
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y)) && cnt_x){
res+=pw[q-SS+x+y]*mult;
res%=mod;
} else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y))==0 && cnt){
res+=pw[q-SS+x+y]*mult;
res%=mod;
}
}
}
}
}
cout<<res<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt=1;
while (tt--){
solve();
}
return 0;
}
/*
2
1 3
1
1 2 2
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8940 KB |
Output is correct |
2 |
Correct |
9 ms |
9452 KB |
Output is correct |
3 |
Correct |
10 ms |
10476 KB |
Output is correct |
4 |
Correct |
12 ms |
10476 KB |
Output is correct |
5 |
Correct |
10 ms |
10476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8940 KB |
Output is correct |
2 |
Correct |
9 ms |
9452 KB |
Output is correct |
3 |
Correct |
10 ms |
10476 KB |
Output is correct |
4 |
Correct |
12 ms |
10476 KB |
Output is correct |
5 |
Correct |
10 ms |
10476 KB |
Output is correct |
6 |
Correct |
25 ms |
27884 KB |
Output is correct |
7 |
Correct |
25 ms |
27884 KB |
Output is correct |
8 |
Correct |
25 ms |
27884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
27884 KB |
Output is correct |
2 |
Correct |
28 ms |
28012 KB |
Output is correct |
3 |
Correct |
24 ms |
27884 KB |
Output is correct |
4 |
Correct |
26 ms |
28140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
700 ms |
202368 KB |
Output is correct |
2 |
Correct |
741 ms |
202220 KB |
Output is correct |
3 |
Correct |
633 ms |
202220 KB |
Output is correct |
4 |
Correct |
637 ms |
202220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
14316 KB |
Output is correct |
2 |
Correct |
13 ms |
14316 KB |
Output is correct |
3 |
Correct |
13 ms |
14316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
14316 KB |
Output is correct |
2 |
Correct |
13 ms |
14316 KB |
Output is correct |
3 |
Correct |
13 ms |
14316 KB |
Output is correct |
4 |
Correct |
14 ms |
14316 KB |
Output is correct |
5 |
Correct |
14 ms |
14316 KB |
Output is correct |
6 |
Correct |
14 ms |
14316 KB |
Output is correct |
7 |
Correct |
14 ms |
14316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8940 KB |
Output is correct |
2 |
Correct |
9 ms |
9452 KB |
Output is correct |
3 |
Correct |
10 ms |
10476 KB |
Output is correct |
4 |
Correct |
12 ms |
10476 KB |
Output is correct |
5 |
Correct |
10 ms |
10476 KB |
Output is correct |
6 |
Correct |
25 ms |
27884 KB |
Output is correct |
7 |
Correct |
25 ms |
27884 KB |
Output is correct |
8 |
Correct |
25 ms |
27884 KB |
Output is correct |
9 |
Correct |
13 ms |
14316 KB |
Output is correct |
10 |
Correct |
13 ms |
14316 KB |
Output is correct |
11 |
Correct |
13 ms |
14316 KB |
Output is correct |
12 |
Correct |
25 ms |
27884 KB |
Output is correct |
13 |
Correct |
24 ms |
27884 KB |
Output is correct |
14 |
Correct |
25 ms |
27884 KB |
Output is correct |
15 |
Correct |
26 ms |
27884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8940 KB |
Output is correct |
2 |
Correct |
9 ms |
9452 KB |
Output is correct |
3 |
Correct |
10 ms |
10476 KB |
Output is correct |
4 |
Correct |
12 ms |
10476 KB |
Output is correct |
5 |
Correct |
10 ms |
10476 KB |
Output is correct |
6 |
Correct |
25 ms |
27884 KB |
Output is correct |
7 |
Correct |
25 ms |
27884 KB |
Output is correct |
8 |
Correct |
25 ms |
27884 KB |
Output is correct |
9 |
Correct |
13 ms |
14316 KB |
Output is correct |
10 |
Correct |
13 ms |
14316 KB |
Output is correct |
11 |
Correct |
13 ms |
14316 KB |
Output is correct |
12 |
Correct |
14 ms |
14316 KB |
Output is correct |
13 |
Correct |
14 ms |
14316 KB |
Output is correct |
14 |
Correct |
14 ms |
14316 KB |
Output is correct |
15 |
Correct |
14 ms |
14316 KB |
Output is correct |
16 |
Correct |
25 ms |
27884 KB |
Output is correct |
17 |
Correct |
24 ms |
27884 KB |
Output is correct |
18 |
Correct |
25 ms |
27884 KB |
Output is correct |
19 |
Correct |
26 ms |
27884 KB |
Output is correct |
20 |
Correct |
251 ms |
106476 KB |
Output is correct |
21 |
Correct |
234 ms |
106604 KB |
Output is correct |
22 |
Correct |
214 ms |
106604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
8940 KB |
Output is correct |
2 |
Correct |
9 ms |
9452 KB |
Output is correct |
3 |
Correct |
10 ms |
10476 KB |
Output is correct |
4 |
Correct |
12 ms |
10476 KB |
Output is correct |
5 |
Correct |
10 ms |
10476 KB |
Output is correct |
6 |
Correct |
25 ms |
27884 KB |
Output is correct |
7 |
Correct |
25 ms |
27884 KB |
Output is correct |
8 |
Correct |
25 ms |
27884 KB |
Output is correct |
9 |
Correct |
55 ms |
27884 KB |
Output is correct |
10 |
Correct |
28 ms |
28012 KB |
Output is correct |
11 |
Correct |
24 ms |
27884 KB |
Output is correct |
12 |
Correct |
26 ms |
28140 KB |
Output is correct |
13 |
Correct |
700 ms |
202368 KB |
Output is correct |
14 |
Correct |
741 ms |
202220 KB |
Output is correct |
15 |
Correct |
633 ms |
202220 KB |
Output is correct |
16 |
Correct |
637 ms |
202220 KB |
Output is correct |
17 |
Correct |
13 ms |
14316 KB |
Output is correct |
18 |
Correct |
13 ms |
14316 KB |
Output is correct |
19 |
Correct |
13 ms |
14316 KB |
Output is correct |
20 |
Correct |
14 ms |
14316 KB |
Output is correct |
21 |
Correct |
14 ms |
14316 KB |
Output is correct |
22 |
Correct |
14 ms |
14316 KB |
Output is correct |
23 |
Correct |
14 ms |
14316 KB |
Output is correct |
24 |
Correct |
25 ms |
27884 KB |
Output is correct |
25 |
Correct |
24 ms |
27884 KB |
Output is correct |
26 |
Correct |
25 ms |
27884 KB |
Output is correct |
27 |
Correct |
26 ms |
27884 KB |
Output is correct |
28 |
Correct |
251 ms |
106476 KB |
Output is correct |
29 |
Correct |
234 ms |
106604 KB |
Output is correct |
30 |
Correct |
214 ms |
106604 KB |
Output is correct |
31 |
Correct |
651 ms |
203576 KB |
Output is correct |
32 |
Correct |
627 ms |
203500 KB |
Output is correct |
33 |
Correct |
606 ms |
203408 KB |
Output is correct |
34 |
Correct |
576 ms |
203244 KB |
Output is correct |
35 |
Correct |
593 ms |
203116 KB |
Output is correct |
36 |
Correct |
581 ms |
203244 KB |
Output is correct |