Submission #531786

#TimeUsernameProblemLanguageResultExecution timeMemory
531786abc864197532Intergalactic ship (IZhO19_xorsum)C++17
100 / 100
1397 ms194040 KiB
#include <bits/stdc++.h> using namespace std; #define lli long long int #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { for (; l != r; ++l) cout << *l << " \n"[l + 1 == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.X >> a.Y; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.X << ", " << a.Y << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; if (a.empty()) return o << "{}"; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } template <typename T> struct vv : vector <vector <T>> { vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {} vv() {} }; template <typename T> struct vvv : vector <vv <T>> { vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {} vvv() {} }; #ifdef Doludu #define test(args...) abc("[" + string(#args) + "]", args) #define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); #else #define test(args...) void(0) #define owo ios::sync_with_stdio(false); cin.tie(0) #endif const int mod = 1e9 + 7, N = 1001, logN = 20, K = 111, C = 7; void trans (vector <lli> &dp, int x) { vector <lli> pre = dp; for (int i = 0; i < C; ++i) { dp[i ^ x] += pre[i]; if (dp[i ^ x] >= mod) dp[i ^ x] -= mod; } } int pre[N][N][C][C], pw[N << 7]; int main () { owo; pw[0] = 1; for (int i = 1; i < N << 7; ++i) { pw[i] = pw[i - 1] + pw[i - 1]; if (pw[i] >= mod) pw[i] -= mod; } int n, q; cin >> n; vector <int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; cin >> q; for (int i = 0, l, r, x; i < q; ++i) { cin >> l >> r >> x, --l; // pre[l ~ r][l ~ r]++ for (int ii = 0; ii < C; ++ii) if (x >> ii & 1) for (int jj = 0; jj < C; ++jj) if (x >> jj & 1) pre[l][l][ii][jj]++, pre[l][r][ii][jj]--, pre[r][l][ii][jj]--, pre[r][r][ii][jj]++; } for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int ii = 0; ii < C; ++ii) for (int jj = 0; jj < C; ++jj) { if (i && j) pre[i][j][ii][jj] -= pre[i - 1][j - 1][ii][jj]; if (i) pre[i][j][ii][jj] += pre[i - 1][j][ii][jj]; if (j) pre[i][j][ii][jj] += pre[i][j - 1][ii][jj]; } lli ans = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { for (int ii = 0; ii < C; ++ii) for (int jj = 0; jj < C; ++jj) { int cnt11 = pre[i][j][ii][jj], cnt10 = pre[i][i][ii][ii] - cnt11, cnt01 = pre[j][j][jj][jj] - cnt11, cnt00 = q - cnt01 - cnt10 - cnt11; int curi[2], curj[2]; if (cnt10) curi[0] = curi[1] = pw[cnt10 - 1]; else curi[0] = 1, curi[1] = 0; if (cnt01) curj[0] = curj[1] = pw[cnt01 - 1]; else curj[0] = 1, curj[1] = 0; int bi = a[i] >> ii & 1, bj = a[j] >> jj & 1, now = 0; if (cnt11) { now = (1ll * curi[bi] * curj[bj] + 1ll * curi[bi ^ 1] * curj[bj ^ 1]) % mod * pw[cnt11 - 1] % mod; } else { now = 1ll * curi[bi ^ 1] * curj[bj ^ 1] % mod; } (ans += 1ll * now % mod * pw[ii + jj] % mod * (min(i, j) + 1) % mod * (n - max(i, j)) % mod * pw[cnt00]) %= mod; } } cout << ans << '\n'; }
#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...