# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
344212 | Nurlykhan | Intergalactic ship (IZhO19_xorsum) | C++17 | 2077 ms | 1516 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;
const int N = (int)1e5 + 10;
const int M = 256;
const int mod = (int)1e9 + 7;
int n, q;
int a[N], b[N];
int l[N], r[N], x[N];
int dp[M + M], old_dp[M + M];
int get_sum(int id) {
memset(old_dp, 0, sizeof(old_dp));
old_dp[a[id]] = 1;
for (int i = 0; i < q; i++) {
if (l[i] <= id && id <= r[i]) {
memset(dp, 0, sizeof(dp));
for (int j = 0; j < M; j++) {
(dp[j ^ x[i]] += old_dp[j]) %= mod;
}
for (int j = 0; j < M; j++) {
(old_dp[j] += dp[j]) %= mod;
}
}
}
int ans = 0;
for (int i = 0; i < M; i++) {
(ans += i * 1ll * old_dp[i] % mod) %= mod;
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &q);
for (int i = 0; i < q; i++)
scanf("%d%d%d", &l[i], &r[i], &x[i]);
int ans = 0;
for (int i = 1; i <= n; i++) {
//cout << i << ' ' << get_sum(i) << endl;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//cout << i << ' ' << j << ' ' << get_sum(i) * 1ll * get_sum(j) * min(i, j) * min(n - i + 1, n - j + 1)
(ans += get_sum(i) * 1ll * get_sum(j) * min(i, j) * min(n - i + 1, n - j + 1) % mod) %= mod;
}
}
cout << ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |