Submission #146167

#TimeUsernameProblemLanguageResultExecution timeMemory
146167imeimi2000Intergalactic ship (IZhO19_xorsum)C++17
0 / 100
950 ms4372 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long llong; const int mod = 1e9 + 7; int n, q; int A[1001]; struct _qs { int l, r, x; void scan() { cin >> l >> r >> x; } } qs[100000]; int P2[100001]; int cnt[1001][1001]; int S[7][1002]; int solve(int a, int b) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { cnt[j][i] = 0; } } int k = q; for (int it = 0; it < q; ++it) { _qs i = qs[it]; bool b1 = (i.x >> a) & 1, b2 = (i.x >> b) & 1; if (!b1 || !b2) continue; ++cnt[i.l][i.r]; --k; } for (int l = 1; l <= n; ++l) { for (int r = n - 1; l <= r; --r) { cnt[l][r] = (cnt[l][r] + cnt[l][r + 1]) % mod; } } for (int l = 2; l <= n; ++l) { for (int r = n; l <= r; --r) { cnt[l][r] = (cnt[l][r] + cnt[l - 1][r]) % mod; } } k = P2[k]; for (int l = 1; l <= n; ++l) { for (int r = n; l <= r; --r) { cnt[l][r] = (llong)cnt[l][r] * k % mod; } } llong ret = 0; for (int l = 1; l <= n; ++l) { for (int r = 1; r <= n; ++r) { if (l > r) cnt[l][r] = cnt[r][l]; llong C[2][2] = {}; C[1][1] = cnt[l][r]; C[1][0] = (S[a][l] + mod - C[1][1]) % mod; C[0][1] = (S[b][r] + mod - C[1][1]) % mod; C[0][0] = P2[q]; C[0][0] += mod - C[0][1]; C[0][0] %= mod; C[0][0] += mod - C[1][0]; C[0][0] %= mod; C[0][0] += mod - C[1][1]; C[0][0] %= mod; int x = (A[l] >> a) & 1; int y = (A[r] >> b) & 1; int v = (n - max(l, r) + 1) * min(l, r); ret += (C[x ^ 1][y ^ 1] << a + b) % mod * v; ret %= mod; } } if (a != b) ret = (ret << 1) % mod; return ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) { cin >> A[i]; } cin >> q; P2[0] = 1; for (int i = 0; i < q; ++i) { qs[i].scan(); P2[i + 1] = (P2[i] << 1) % mod; for (int j = 0; j < 7; ++j) { if ((qs[i].x >> j) & 1) { ++S[j][qs[i].l]; --S[j][qs[i].r + 1]; } } } for (int j = 0; j < 7; ++j) { for (int i = 1; i <= n; ++i) { S[j][i] += S[j][i - 1]; } } llong ans = 0; for (int i = 0; i < 7; ++i) { for (int j = 0; j <= i; ++j) { ans += solve(j, i); } } printf("%lld\n", ans % mod); return 0; }

Compilation message (stderr)

xorsum.cpp: In function 'int solve(int, int)':
xorsum.cpp:67:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
             ret += (C[x ^ 1][y ^ 1] << a + b) % mod * v;
                                        ~~^~~
#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...