Submission #679465

#TimeUsernameProblemLanguageResultExecution timeMemory
679465grandmast3rIntergalactic ship (IZhO19_xorsum)C++17
0 / 100
2058 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define pii pair<int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using namespace std; const int MOD = 1e9 + 7; int add(int a, int b){ a += b; if (a >= MOD){ a -= MOD; } return a; } int sub(int a, int b){ a -= b; if (a < 0){ a += MOD; } return a; } int mul(int a, int b){ return (a * 1ll * b) % MOD; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifdef ON_PC freopen("input.txt", "r", stdin); #endif // freopen("output.txt", "w", stdout); int T = 1; // cin >> T; while (T--){ int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++){ cin >> a[i]; } int q; cin >> q; vector<vector<int>> req(q); for (int id = 0; id < q; id++){ req[id].resize(3); for (int i = 0; i < 3; i++){ cin >> req[id][i]; } } vector<vector<vector<int>>> pref((1 << 7), vector<vector<int>>(n + 1, vector<int>(n + 1))); for (int i = 0; i < q; i++){ pref[req[i][2]][req[i][0]][req[i][1]]++; } for (int x = 0; x < (1 << 7); x++){ for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ pref[x][i][j] += pref[x][i][j - 1]; } } for (int j = 1; j <= n; j++){ for (int i = 1; i <= n; i++){ pref[x][i][j] += pref[x][i - 1][j]; } } } function<int(int, int, int, int, int)> count = [&](int x, int i1, int j1, int i2, int j2){ if (i1 > i2 || j1 > j2){ return 0; } return pref[x][i2][j2] - pref[x][i1 - 1][j2] - pref[x][i2][j1 - 1] + pref[x][i1 - 1][j1 - 1]; }; int res = 0; for (int i = 1; i <= n; i++){ for (int j = i; j <= n; j++){ vector<vector<vector<int>>> dp0((1 << 7), vector<vector<int>>(7, vector<int>(2))); vector<vector<vector<int>>> dp1((1 << 7), vector<vector<int>>(7, vector<int>(2))); for (int k = 0; k < 7; k++){ dp0[a[i]][k][bool(a[j] & (1 << k))]++; } dp1 = dp0; for (int h = 0; h < (1 << 7); h++){ for (int s = 0; s < (1 << 7); s++){ int x = 0; int y = 0; int cnt = 0; // y = 0; for (int k = 0; k < 7; k++){ // x = 0, y = 0 x = 0; cnt = count(s, 1, 1, i - 1, i - 1) + count(s, i + 1, i + 1, j - 1, j - 1) + count(s, j + 1, j + 1, n, n); dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt)); dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt)); // x = s, y = 0; x = s; cnt = count(s, 1, i, i, j - 1); dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt)); dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt)); } for (int k = 0; k < 7; k++){ if (s & (1 << k)){ swap(dp0[h][k][0], dp0[h][k][1]); } // x = 0, y = s cnt = count(s, i + 1, j, j, n); x = 0; dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt)); dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt)); // x = s, y = s; cnt = count(s, 1, j, i, n); x = s; dp1[h ^ x][k][0] = add(dp1[h ^ x][k][0], mul(dp0[h][k][0], cnt)); dp1[h ^ x][k][1] = add(dp1[h ^ x][k][1], mul(dp0[h][k][1], cnt)); if (s & (1 << k)){ swap(dp0[h][k][0], dp0[h][k][1]); } } } } dp1.swap(dp0); int segcnt = mul(i, n - j + 1); int t = mul(segcnt, 1 + (i != j)); for (int s = 0; s < (1 << 7); s++){ for (int k = 0; k < 7; k++){ res = add(res, mul(mul(s, mul(dp0[s][k][1], (1 << k))), t)); } } // for (int mask = 0; mask < (1 << q); mask++){ // int x = a[i]; // int y = a[j]; // for (int k = 0; k < q; k++){ // if (mask & (1 << k)){ // if (req[k][0] <= i && i <= req[k][1]){ // x ^= req[k][2]; // } // if (req[k][0] <= j && j <= req[k][1]){ // y ^= req[k][2]; // } // } // } // int segcnt = mul(i, n - j + 1); // res = add(res, mul(mul(2, segcnt), mul(x, y))); // } } } cout << res << "\n"; } return 0; }

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:94:29: warning: unused variable 'y' [-Wunused-variable]
   94 |                         int y = 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...