#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;
//#define int long long
const int BT = 8;
const int mod = (int)1e9 + 7;
const int N = 1001;
const int NN = 1e5 + 10;
int fact[NN] , pw2[NN] , CHOOSE[NN][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){
// a %= mod;
if(a >= mod)
a-=mod;
}
void prep(){
fact[0] = 1;
for(int i = 1; i < NN; ++i)
fact[i] = (1ll * fact[i-1] * i) % mod;
pw2[0] = 1;
for(int i =1; i < NN; ++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);
}
void brute(vector < int > &a , vector < pair < int , int > > &lines , vector < int > &X){
int answer = 0;
int S2 = 0 , Mult = 0;
for(int msk = 0 ; msk < (1 << len(lines)); ++msk){
vector < int > nw = a;
for(int j = 0 ; j < len(lines); ++j){
if((1 << j) & msk){
for(int f = lines[j].fi; f <= lines[j].se; ++f)
nw[f] ^= X[j];
}
}
for(int f = 0 ; f < len(a); ++f)
S2 += (f + 1) * (len(a) - f) * nw[f] * nw[f];
for(int f = 0 ; f < len(a); ++f)
for(int j = f + 1; j < len(a); ++j)
Mult +=2 * (f + 1) * (len(a) - j) * nw[f] * nw[j];
for(int f = 0 ; f < len(a); ++f){
int cursum = 0;
for(int z = f; z < len(a); ++z){
cursum += nw[z] , md(cursum);
answer += 1ll * cursum * cursum % mod;
md(answer);
}
}
}
#ifdef LOCAL
cout << " BRUTE ";
#endif // LOCAL
cout << S2 << ' ' << Mult << ' ';
cout << answer;
}
int both[BT][BT][4];
int fir[BT][2];
int sec[BT][2];
vector < int > del[N] , DEL[N] , ADD[N];
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;
lines.pb({l , r});
X.pb(x);
}
// brute(a , lines , X);
// cout << endl;
int Sin2 = 0;
int Smult = 0;
auto add = [&](int ind ,int val){
for(int b1=0;b1<BT;++b1)
for(int b2=0;b2<BT;++b2){
int bit1,bit2;
bit1 = ((1 << b1) & X[ind]) > 0;
bit2 = ((1 << b2) & X[ind]) > 0;
both[b1][b2][(bit1<<1)|bit2]+=val;
}
};
auto addFir = [&](int ind , int val){
for(int b1=0;b1<BT;++b1){
int bit1;
bit1 = ((1 << b1) & X[ind]) > 0;
fir[b1][bit1]+=val;
}
};
auto addSec = [&](int ind , int val){
for(int b1=0;b1<BT;++b1){
int bit1;
bit1 = ((1 << b1) & X[ind]) > 0;
sec[b1][bit1]+=val;
}
};
for(int ind = 0 ; ind < len(lines); ++ind){
ADD[lines[ind].fi].pb(ind) , DEL[lines[ind].se+1].pb(ind);
}
for(int i = 0 ; i < n; ++i){
/// like YO
for(int z = 0 ; z < BT; ++z)
for(int zz = 0 ; zz < BT; ++zz)
for(int zzz = 0; zzz < 4; ++zzz)
both[z][zz][zzz]= 0;
for(int z = 0; z < BT; ++z)
for(int zz = 0 ; zz < 2; ++zz)
fir[z][zz] = 0;
for(int z = 0; z < BT; ++z)
for(int zz = 0 ; zz < 2; ++zz)
sec[z][zz] = 0;
vector < vector < int > > del(n + 1);
int CNTBOTH = 0;
for(int j = 0 ; j < len(lines); ++j){
if(lines[j].fi <= i && lines[j].se >= i){
add(j , +1);
CNTBOTH++;
del[lines[j].se+1].pb(j);
}
}
/// calculate SEC
for(int j = i; j < n; ++j){
if(j > i){
for(auto u : ADD[j])
addSec(u , +1);
for(auto u : DEL[j])
addSec(u , -1);
}
for(auto u : del[j]){
add(u , -1);
addFir(u , +1);
CNTBOTH--;
}
int CNTALL = fir[0][0]+fir[0][1]+sec[0][0]+sec[0][1]+CNTBOTH;
int nowhere = q - CNTALL;
/// it's dp motherfuckaaa
for(int B1=0;B1<BT;++B1){
for(int B2=0;B2<BT;++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 = 1ll*pw2[fir[B1][0]]*CHOOSE[fir[B1][1]][bit1^BIT1]%mod;
for(int bit2=0;bit2<=1;++bit2){
int cur2 = 1ll*pw2[sec[B2][0]]*CHOOSE[sec[B2][1]][bit2^BIT2]%mod;
/// 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 == 0 && j == 1 && max(B1,B2) < 2){
// cout << " BIT'S \n";
// cout << B1 << ' ' << bit1 << '\n';
// cout << B2 << ' ' << bit2 << '\n';
//
// cout << nowhere << '\n';
// cout << cur1 << ' ' << cur2 << ' ' << dp[bt][((bit1^1)<<1)|(bit2^1)] << '\n';
// cout << " XM " << pw2[sec[B1][0]] << ' ' << CHOOSE[sec[B2][1]][bit2^BIT2] << ' ' << BIT2 << endl;
// cout << " THAT " << that << endl;
// }
}
}
}
}
}
}
// cout << " YO " << Sin2 << endl;
int answer = (1ll*Sin2 + 1ll*Smult*2)%mod;
cout << answer;
// assert(answer != 52);
return 0;
}
/*
3
1 2 3
3
2 3 1
1 2 4
1 3 7
2
1 2
2
1 2 4
2 2 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
656 ms |
4324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
2028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
2048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2028 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
2028 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
