#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1003, M = 100003, K = 128, MOD = 1e9 + 7;
int n, q, a[N], pw[M];
vector <pii> R[N];
int bit[K], mask[K];
struct basis {
int sz = 0;
vector <int> b;
bitset <K> can;
basis() {
can[0] = 1;
}
void clear() {
sz = 0;
b.clear();
can.reset();
can[0] = 1;
}
void upd() {
can.reset();
for (int i = 0; i < (1 << sz); i++) {
if (i > 0) {
mask[i] = mask[i ^ (1 << bit[i])] ^ b[bit[i]];
}
can[mask[i]] = 1;
}
}
bool add(int x) {
sz++;
for (int i : b) {
x = min(x, x ^ i);
}
if (x) {
b.pb(x);
upd();
return true;
}
return false;
}
int ways() {
return pw[sz - (int)b.size()];
}
};
basis C[N][N], cur, A[N];
int last[N], f[K][N], g[K];
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
for (int i = 1; i < K; i++) {
for (int j = 6; j >= 0; j--) {
if (i >> j & 1) {
bit[i] = j;
break;
}
}
}
pw[0] = 1;
for (int i = 1; i < M; i++) {
pw[i] = pw[i - 1] * 2 % MOD;
}
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r, x;
cin >> l >> r >> x;
R[r].pb({l, x});
}
for (int l = 1; l <= n; l++) {
cur.clear();
for (int r = n; r >= l; r--) {
for (auto i : R[r]) {
if (i.F <= l) {
cur.add(i.S);
}
}
C[l][r] = cur;
}
}
int ans = 0;
for (int l = 1; l <= n; l++) {
cur.clear();
memset(& last, 0, sizeof(last));
last[l] = l;
for (int r = l; r <= n; r++) {
if (last[r] == r) {
A[r] = cur;
for (int i = 0; i < K; i++) {
f[i][r] = 0;
for (int j = 0; j < K; j++) {
f[i][r] += j * cur.can[j ^ i];
}
}
} else {
last[r] = last[r - 1];
}
for (auto i : R[r]) {
if (i.F <= l) {
if (cur.add(i.S)) {
last[r + 1] = r + 1;
}
}
}
}
cur.clear();
for (int k = 0; k < K; k++) {
g[k] = 0;
for (int j = 0; j < K; j++) {
g[k] += j * cur.can[j ^ k];
}
}
for (int r = n; r >= l; r--) {
for (auto i : R[r]) {
if (i.F > l) {
if (cur.add(i.S)) {
for (int k = 0; k < K; k++) {
g[k] = 0;
for (int j = 0; j < K; j++) {
g[k] += j * cur.can[j ^ k];
}
}
}
}
}
int res = 0, pos = last[r];
for (int i = 0; i < K; i++) {
res += C[l][r].can[i] * f[i ^ a[l]][pos] * g[i ^ a[r]] % MOD;
if (res >= MOD) {
res -= MOD;
}
}
res = (ll)res * C[l][r].ways() % MOD;
res = (ll)res * A[pos].ways() % MOD;
res = (ll)res * cur.ways() % MOD;
//cerr << "l r " << l << ' ' << r << '\n';
//cerr << q << ' ' << C[l][r].sz << ' ' << A[pos].sz << ' ' << cur.sz << '\n';
//cerr << "pos " << pos << '\n';
res = (ll)res * pw[q - C[l][r].sz - A[pos].sz - cur.sz] % MOD;
if (l == r) {
res = (ll)res * ((MOD + 1) / 2) % MOD;
}
int occ = l * (n - r + 1);
ans += (ll)res * occ % MOD;
if (ans >= MOD) {
ans -= MOD;
}
}
}
cout << 2 * ans % MOD;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
48512 KB |
Output is correct |
| 2 |
Correct |
32 ms |
48512 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
97144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
48512 KB |
Output is correct |
| 2 |
Correct |
32 ms |
48512 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
97144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
99480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
98424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
97204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
97204 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
48512 KB |
Output is correct |
| 2 |
Correct |
32 ms |
48512 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
97144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
48512 KB |
Output is correct |
| 2 |
Correct |
32 ms |
48512 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
97144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
48512 KB |
Output is correct |
| 2 |
Correct |
32 ms |
48512 KB |
Output is correct |
| 3 |
Runtime error |
82 ms |
97144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
