| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 990675 | ToniB | Intergalactic ship (IZhO19_xorsum) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>using namespace std; typedef long long ll;const int MOD = 1e9 + 7;const int N = 105;const int K = 32;const int Q = 1e5 + 5; inline int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b;}inline int mul(int a, int b) { return (long long) a * b % MOD;} int n, a[N], q, l[N], r[N], x[N], pre[N], ans;int dp[N][N][N * K], pt[Q];vector<int> queries[N]; void solveSimpleSegments() { pt[0] = 1; for (int i = 1; i <= q; ++i) pt[i] = mul(pt[i - 1], 2); for (int i = 0; i < q; ++i) { queries[l[i]].push_back(x[i]); } pre[0] = queries[0].size(); for (int i = 1; i < n; ++i) pre[i] = queries[i].size() + pre[i - 1]; for (int i = 0; i < n; ++i) { dp[i][i][a[i]] = 1; for (int val : queries[i]) { vector<int> tmp (K, 0); for (int j = 0; j < K; ++j) { tmp[j] = add(dp[i][i][j], dp[i][i][j ^ val]); } for (int j = 0; j < K; ++j) dp[i][i][j] = tmp[j]; } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int sum = 0; sum < n * K; ++sum) { for (int k = 0; k < min(K, sum); ++k) { dp[i][j][sum] = add(dp[i][j][sum], mul(dp[i][j - 1][sum - k], dp[j][j][k])); } } } } int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { for (int sum = 0; sum < n * K; ++sum) { int rem = q - (pre[j] - (i ? pre[i - 1] : 0)); int val = mul(sum, sum); int count = mul(dp[i][j][sum], pt[rem]); ans = add(ans, mul(val, count)); } } } cout << ans << "\n";} int main(){ cin >> n; for (int i = 0; i < n; ++i) cin >> a[i];
cin >> q;
int maxlen = 0;
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i] >> x[i], --l[i], --r[i];
maxlen = max(maxlen, r[i] - l[i]);
}
if (!maxlen) {
solveSimpleSegments();
return 0;
}
for (int i = 0; i < (1 << q); ++i) {
for (int j = 0; j < q; ++j) {
if (i & 1 << j) {
pre[l[j]] ^= x[j];
pre[r[j] + 1] ^= x[j];
}
}
for (int i = 1; i < n; ++i) pre[i] ^= pre[i - 1];
for (int i = 0; i < n; ++i) a[i] ^= pre[i];
int sum = 0;
for (int i = 0; i < n; ++i) {
int cur = 0;
for (int j = i; j < n; ++j) {
cur += a[j];
sum += cur * cur;
sum %= MOD;
}
}
ans += sum;
ans %= MOD;
for (int i = 0; i < n; ++i) {
a[i] ^= pre[i];
pre[i] = 0;
}
}
cout << ans << "\n";
return 0;
}