#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const ll mod = 1e9 + 7;
const int maxn = 1010;
const int maxbit = 7;
const int maxq = 1e5 + 10;
int n, q;
int a[maxn];
struct query_data
{
int l, r, x;
void input()
{
cin >> l >> r >> x;
}
} task[maxq];
bool is_affected(int i, int bit_i, int t)
{
if (task[t].r < i || task[t].l > i)
return false;
if ((task[t].x & (1 << bit_i)) == 0)
return false;
return true;
}
ll fac[maxq], inv[maxq];
ll power(ll base, ll st)
{
ll res = 1;
while(st > 0)
{
if (st % 2 == 1)
res = (res * base) % mod;
base = (base * base) % mod;
st /= 2;
}
return res;
}
ll comb(ll from, ll take)
{
if (take < 0 || take > from)
return 0;
return ((fac[from] * inv[take]) % mod * inv[from - take]) % mod;
}
ll pw[maxq];
bitset < maxq > bt[maxbit][maxn];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i];
cin >> q;
fac[0] = inv[0] = pw[0] = 1;
for (int i = 1; i < max(q + 1, maxbit * 2); i ++)
{
pw[i] = (pw[i - 1] * 2) % mod;
}
for (int i = 1; i <= q; i ++)
{
fac[i] = (fac[i - 1] * (ll)(i)) % mod;
inv[i] = power(fac[i], mod - 2);
}
for (int i = 1; i <= q; i ++)
{
task[i].input();
}
for (int i = 1; i <= n; i ++)
{
for (int bit = 0; bit < maxbit; bit ++)
{
for (int j = 1; j <= q; j ++)
bt[bit][i][j] = is_affected(i, bit, j);
}
}
ll ans = 0;
for (int i = 1; i <= n; i ++)
{
for (int j = i; j <= n; j ++)
{
for (int bit_i = 0; bit_i < maxbit; bit_i ++)
{
for (int bit_j = 0; bit_j < maxbit; bit_j ++)
{
int both = 0;
int ch_i = 0;
int ch_j = 0;
int neit = 0;
ch_i = bt[bit_i][i].count();
ch_j = bt[bit_j][j].count();
both = (bt[bit_i][i] & bt[bit_j][j]).count();
ch_i -= both;
ch_j -= both;
neit = q - both - ch_i - ch_j;
/**for (int t = 1; t <= q; t ++)
{
bool af_i = is_affected(i, bit_i, t), af_j = is_affected(j, bit_j, t);
if (af_i == false && af_j == false)
neit ++;
else if (af_i == true && af_j == false)
ch_i ++;
else if (af_i == false && af_j == true)
ch_j ++;
else if (af_i == true && af_j == true)
both ++;
}*/
int val_i = ((a[i] & (1 << bit_i)) > 0);
int val_j = ((a[j] & (1 << bit_j)) > 0);
ll res = 0;
for (int d_i = 0; d_i < 2; d_i ++)
for (int d_j = 0; d_j < 2; d_j ++)
for (int b = 0; b < 2; b ++)
{
if ((val_i + d_i + b) % 2 == 0 ||
(val_j + d_j + b) % 2 == 0)
continue;
ll way_i = 0;
ll way_j = 0;
ll way_b = 0;
for (int l = d_i; l <= ch_i; l += 2)
{
way_i += comb(ch_i, l);
if (way_i >= mod)
way_i -= mod;
}
for (int l = d_j; l <= ch_j; l += 2)
{
way_j += comb(ch_j, l);
if (way_j >= mod)
way_j -= mod;
}
for (int l = b; l <= both; l += 2)
{
way_b += comb(both, l);
if (way_b >= mod)
way_b -= mod;
}
///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
{
///cout << "ways " << way_i << " " << way_j << " " << way_b << endl;
}
ll ways = ((way_i * way_j) % mod * way_b) % mod;
res = res + ways;
if (res >= mod)
res -= mod;
}
res = (res * (pw[bit_i + bit_j])) % mod;
res = (res * pw[neit]) % mod;
res = (res * (ll)(i) * (ll)(n - j + 1)) % mod;
if (i != j)
res = (res * 2) % mod;
ans += res;
if (ans >= mod)
ans -= mod;
///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0)
{
///cout << i << " " << j << " " << bit_i << " " << bit_j << " " << res << endl;
///cout << pw[bit_i + bit_j] << " " << (i * (n - i + 1)) << endl;
///cout << ans << endl;
}
}
}
}
}
cout << ans << endl;
}
int main()
{
speed();
solve();
return 0;
}
/**
2
1 3
2
1 2 2
1 1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
31 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18776 KB |
Output is correct |
| 5 |
Correct |
32 ms |
18780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
31 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18776 KB |
Output is correct |
| 5 |
Correct |
32 ms |
18780 KB |
Output is correct |
| 6 |
Execution timed out |
2041 ms |
22876 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
24736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2035 ms |
55640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
257 ms |
22872 KB |
Output is correct |
| 3 |
Correct |
298 ms |
22876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
257 ms |
22872 KB |
Output is correct |
| 3 |
Correct |
298 ms |
22876 KB |
Output is correct |
| 4 |
Correct |
375 ms |
23172 KB |
Output is correct |
| 5 |
Correct |
400 ms |
23132 KB |
Output is correct |
| 6 |
Correct |
373 ms |
23128 KB |
Output is correct |
| 7 |
Correct |
446 ms |
23152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
31 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18776 KB |
Output is correct |
| 5 |
Correct |
32 ms |
18780 KB |
Output is correct |
| 6 |
Execution timed out |
2041 ms |
22876 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
31 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18776 KB |
Output is correct |
| 5 |
Correct |
32 ms |
18780 KB |
Output is correct |
| 6 |
Execution timed out |
2041 ms |
22876 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
31 ms |
18780 KB |
Output is correct |
| 4 |
Correct |
32 ms |
18776 KB |
Output is correct |
| 5 |
Correct |
32 ms |
18780 KB |
Output is correct |
| 6 |
Execution timed out |
2041 ms |
22876 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
