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];
}
int uk = 0;
for (int j = 0; j < K; ++j) uk = add(uk, dp[i][i][j]);
assert(uk == pt[queries[i].size()]);
}
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;
}
# | 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... |