Submission #990683

#TimeUsernameProblemLanguageResultExecution timeMemory
990683ToniBIntergalactic ship (IZhO19_xorsum)C++17
8 / 100
1844 ms127956 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...