#include<bits/stdc++.h>
#define fi first
#define se second
#define len(x) (int)(x).size()
#define pb push_back
#define p2(x) (x)*(x)
#define all(x) (x).begin() , (x).end()
#define mkp make_pair
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
const int N = 1001;
const int NN = 1e3 + 10;
int cnt[N][7][2] , fact[NN] , pw2[NN] , CHOOSE[N][2];
int binpow(int a , int b){
if(b == 0)
return 1;
int ans = binpow(a , b >> 1);
ans = (1ll * ans * ans) % mod;
if(b & 1)
ans = (1ll * ans * a) % mod;
return ans;
}
int INV(int x){
return binpow(x , mod-2);
}
void md(int &a){
if(a >= mod)
a-=mod;
}
void prep(){
fact[0] = 1;
for(int i = 1; i < N; ++i)
fact[i] = (1ll * fact[i-1] * i) % mod;
pw2[0] = 1;
for(int i =1; i < N; ++i)
pw2[i] = (1ll * pw2[i-1] * 2) % mod;
CHOOSE[0][0] = 1;
for(int i = 1; i < NN; ++i){
CHOOSE[i][0] = (CHOOSE[i-1][0] + CHOOSE[i-1][1]);
md(CHOOSE[i][0]);
CHOOSE[i][1] = (CHOOSE[i-1][1] + CHOOSE[i-1][0]);
md(CHOOSE[i][1]);
}
}
int Cnk(int n , int k){
if(k == 0)
return 1;
return (1ll * fact[n] * (INV(fact[k]))%mod * INV(fact[n-k])%mod);
}
signed main()
{
prep();
ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n;
cin >> n;
vector < int > a(n);
for(auto &i : a)cin >> i;
int q;
cin >> q;
vector < pair < int , int > > lines;
vector < int > X;
for(int i = 0 ; i < q; ++i){
int l , r , x;
cin >> l >> r >> x;
--l , --r;
// for(int j = l; j <= r; ++j){
// for(int b = 0 ;b < 7; ++b){
// if((1 << b) & x)
// cnt[j][b][1]++;
// else
// cnt[j][b][0]++;
// }
// }
lines.pb({l , r});
X.pb(x);
}
int Sin2 = 0;
// for(int i = 0 ; i < n; ++i){
// for(int b = 0 ;b < 7; ++b){
// for(int bit=0;bit<=1;++bit){
// int cur=pw2[q - cnt[i][b][1]];
// int var = (1ll * cur * CHOOSE[cnt[i][b][1]][bit]) % mod;
// int val = bit ^ (((1 << b)&a[i])>0);
// if(val != 0)
// Sin2 += 1ll*(i+1)*(n-i)%mod*var%mod*(1<<b)*(1<<b)%mod, Sin2 %=mod;
// }
// }
// cout << "AFTER " << i << ' ' << Sin2 << endl;
// }
// cout << Sin2 << endl;
// cout << " WTF \n";
// cout << CHOOSE[5][1] << endl;
// cout << CHOOSE[5][0] << endl;
int Smult = 0;
for(int i = 0 ; i < n; ++i){
for(int j = i; j < n; ++j){
int fir[7][2] , sec[7][2] , nowhere = 0;
for(int z = 0 ; z < 7; ++z)
for(int zz = 0; zz < 7; ++zz)
fir[z][zz] = sec[z][zz] = 0;
for(int ind = 0 ; ind < len(lines); ++ind){
if(lines[ind].fi <= i && lines[ind].se >= j)
continue;
for(int b = 0 ; b < 7; ++b){
int bit = ((1 << b) & X[ind]) > 0;
if(lines[ind].fi <= i && lines[ind].se >= i)
fir[b][bit]++;
if(lines[ind].fi <= j && lines[ind].se >= j)
sec[b][bit]++;
}
int bad = 0;
if(lines[ind].fi <= i && lines[ind].se >= i)
bad += 0;
else bad += 1;
if(lines[ind].fi <= j && lines[ind].se >= j)
bad += 0;
else bad += 1;
if(bad == 2){
nowhere++;
}
}
int both[7][7][4];
for(int z = 0 ; z < 7; ++z)
for(int zz = 0 ; zz < 7; ++zz)
for(int zzz = 0; zzz < 4; ++zzz)
both[z][zz][zzz]= 0;
for(int ind = 0 ; ind < len(lines); ++ind){
if(lines[ind].fi > i || lines[ind].se < j)
continue;
for(int b1=0;b1<7;++b1)
for(int b2=0;b2<7;++b2){
int bit1,bit2;
bit1 = ((1 << b1) & X[ind]) > 0;
bit2 = ((1 << b2) & X[ind]) > 0;
both[b1][b2][(bit1<<1)|bit2]++;
}
}
/// it's dp motherfuckaaa
for(int B1=0;B1<7;++B1){
for(int B2=0;B2<7;++B2){
/// okay
/// omg that's strange task
/// weird
/// lulz okay
int dp[2][4];
int bt = 0;
fill(dp[0], dp[0]+4 , 0);
dp[0][0] = 1;
for(int msk = 0; msk < 4; ++msk){
/// lulz okay
bt ^= 1;
fill(dp[bt] , dp[bt] + 4 , 0);
for(int prvmsk = 0; prvmsk < 4; ++prvmsk){
dp[bt][prvmsk] += (1ll * dp[bt^1][prvmsk] * CHOOSE[both[B1][B2][msk]][0]) % mod;
md(dp[bt][prvmsk]);
dp[bt][prvmsk^msk] += (1ll * dp[bt^1][prvmsk] * CHOOSE[both[B1][B2][msk]][1]) % mod;
md(dp[bt][prvmsk^msk]);
}
}
int BIT1 , BIT2;
BIT1 = ((1 << B1) & a[i]) > 0;
BIT2 = ((1 << B2) & a[j]) > 0;
for(int bit1=0;bit1<=1;++bit1){
int cur1 = pw2[fir[B1][0]]*CHOOSE[fir[B1][1]][bit1^BIT1];
for(int bit2=0;bit2<=1;++bit2){
int cur2 = pw2[sec[B1][0]]*CHOOSE[sec[B2][1]][bit2^BIT2];
/// and yo
/// lul from both we need bit1^1 , bit2^1
int that = 1ll*pw2[nowhere]*1ll*(i+1)%mod*(n-j)%mod*cur1%mod*cur2%mod*dp[bt][((bit1^1)<<1)|(bit2^1)]%mod*(1<<B1)%mod*(1<<B2)%mod;
if(i == j)
Sin2 += that , md(Sin2);
else
Smult += that , md(Smult);
// if(i == j && i == 0 && B1 < 2 && B2 < 2){
// cout << " FUCK THIS SHIT " << 0 << endl;
// cout << B1 << ' ' << B2 << ' ' << bit1 << ' ' << bit2 << ' ' << dp[bt][((bit1^1)<<1)|(bit2^1)] << endl;
//
// cout << cur1 << ' ' << cur2 << ' ';
// cout << endl;
// cout << " THAT " << that << endl;
// cout << endl;
// }
}
}
}
}
}
}
// cout << " YO " << Sin2 << endl;
int answer = (1ll*Sin2 + 1ll*Smult*2)%mod;
cout << answer;
return 0;
}
/*
*/
Compilation message
xorsum.cpp: In function 'void prep()':
xorsum.cpp:49:38: warning: iteration 1001 invokes undefined behavior [-Waggressive-loop-optimizations]
49 | CHOOSE[i][1] = (CHOOSE[i-1][1] + CHOOSE[i-1][0]);
| ~~~~~~~~~~~~~^
xorsum.cpp:46:22: note: within this loop
46 | for(int i = 1; i < NN; ++i){
| ~~^~~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:113:45: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
113 | fir[z][zz] = sec[z][zz] = 0;
| ~~~~~~~~~~~^~~
xorsum.cpp:112:36: note: within this loop
112 | for(int zz = 0; zz < 7; ++zz)
| ~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
2916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
