#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1<<x)
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int N=1e3+2;
const int Q=1e5+3;
const int M=1e9+7;
//int pref[4][N][N];
int prec[2][Q];
int p2[Q];
vec<array<int,3>>go[4];
int mult(int a,int b){
return 1ll*a*b%M;
}
void add(int &a,int b){
a+=b;
if(a>=M) a-=M;
else if(a<0) a+=M;
}
struct _2d{
int pref[N][N];
void clr(){
for(int i=0;i<N;i++){
fill(pref[i],pref[i]+N,0);
}
}
void build(){
for(int i=0;i<N;i++){
for(int j=1;j<N;j++){
pref[i][j]+=pref[i][j-1];
}
}
for(int i=1;i<N;i++){
for(int j=0;j<N;j++){
pref[i][j]+=pref[i-1][j];
}
}
}
int get(int x1,int x2,int y1,int y2){
if(x1>x2) return 0;
int w=pref[x2][y2];
if(x1) w-=pref[x1-1][y2];
if(y1) w-=pref[x2][y1-1];
if(x1 && y1) w+=pref[x1-1][y1-1];
return w;
}
}st;
struct _1d{
int pref[N];
void clr(){
for(int i=0;i<N;i++) pref[i]=0;
}
void build(){
for(int i=1;i<N;i++){
pref[i]+=pref[i-1];
}
}
int get(int x){
return pref[x];
}
}lol[2];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
p2[0]=1;for(int i=1;i<Q;i++) p2[i]=mult(p2[i-1],2);
vec<int>a(n);
for(auto &z : a)
cin>>z;
int q;
cin>>q;
vec<int>l(q),r(q),x(q);
for(int i=0;i<q;i++){
cin>>l[i]>>r[i]>>x[i];--l[i];--r[i];
}
for(int i=0;i<4;i++){
for(int f=0;f<2;f++){
for(int j=0;j<2;j++){
for(int k=0;k<2;k++){
int msk=i;
if(f) msk^=1;
if(j) msk^=2;
if(k) msk^=3;
if(msk==3){
go[i].pb({f,j,k});
}
}
}
}
}
prec[0][0]=1;
for(int i=0;i<=q;i++){
for(int cr=0;cr<2;cr++){
add(prec[cr][i+1],prec[cr][i]);
add(prec[cr^1][i+1],prec[cr][i]);
}
}
int ans=0;
for(int b1=0;b1<7;b1++){
for(int b2=0;b2<7;b2++){
st.clr();
lol[0].clr();lol[1].clr();
for(int i=0;i<q;i++){
if(x[i]&(1<<b1) && x[i]&(1<<b2)) st.pref[l[i]][r[i]]++;
if(x[i]&(1<<b1)) lol[0].pref[l[i]]++,lol[0].pref[r[i]+1]--;
if(x[i]&(1<<b2)) lol[1].pref[r[i]+1]--,lol[1].pref[l[i]]++;
}
st.build();
lol[0].build();lol[1].build();
int s=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
int start=((a[i]>>b1)&1)+(((a[j]>>b2)&1)<<1);
int x3=st.get(0,i,j,n-1);
int x1=lol[0].pref[i]-x3;
int x2=lol[1].pref[j]-x3;
int x0=q-x1-x2-x3;
int og=0;
for(auto &z : go[start]){
int w=1ll*prec[z[0]][x1]*prec[z[1]][x2]%M*prec[z[2]][x3]%M;
add(og,w);
}
og=mult(og,mult(n-j,mult(i+1,og)));
og=mult(og,p2[x0]);
if(i!=j) og=mult(2,og);
add(s,og);
}
}
add(ans,mult(p2[b1+b2],s));
}
}
cout<<ans;
return 0;
}
/*
5
1 2 3 4 5
1
1 4 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4640 KB |
Output is correct |
| 2 |
Correct |
170 ms |
4628 KB |
Output is correct |
| 3 |
Incorrect |
164 ms |
4632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4640 KB |
Output is correct |
| 2 |
Correct |
170 ms |
4628 KB |
Output is correct |
| 3 |
Incorrect |
164 ms |
4632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
265 ms |
6632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1454 ms |
4648 KB |
Output is correct |
| 2 |
Correct |
1453 ms |
4640 KB |
Output is correct |
| 3 |
Correct |
1414 ms |
4640 KB |
Output is correct |
| 4 |
Correct |
1416 ms |
4648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
4556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4640 KB |
Output is correct |
| 2 |
Correct |
170 ms |
4628 KB |
Output is correct |
| 3 |
Incorrect |
164 ms |
4632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4640 KB |
Output is correct |
| 2 |
Correct |
170 ms |
4628 KB |
Output is correct |
| 3 |
Incorrect |
164 ms |
4632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4640 KB |
Output is correct |
| 2 |
Correct |
170 ms |
4628 KB |
Output is correct |
| 3 |
Incorrect |
164 ms |
4632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
