Submission #679488

#TimeUsernameProblemLanguageResultExecution timeMemory
679488grandmast3rIntergalactic ship (IZhO19_xorsum)C++17
12 / 100
2084 ms5824 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() #define int long long 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 naive(vector<int> a, vector<vector<int>> req){ int n = a.size() - 1; int q = req.size(); 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))]++; } for (int w = 0; w < q; w++){ dp1 = dp0; int x = 0; int y = 0; if (req[w][0] <= i && i <= req[w][1]){ x = req[w][2]; } if (req[w][0] <= j && j <= req[w][1]){ y = req[w][2]; } for (int s = 0; s < (1 << 7); s++){ for (int k = 0; k < 7; k++){ if (y & (1 << k)){ swap(dp0[s][k][0], dp0[s][k][1]); } dp1[s ^ x][k][0] = add(dp1[s ^ x][k][0], dp0[s][k][0]); dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], dp0[s][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)); } } } } return res; } signed 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); vector<int> pw2(1e3 + 10); pw2[0] = 1; for (int i = 1; i < 1e3 + 10; i++){ pw2[i] = mul(pw2[i - 1], 2); } 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]; } } #ifdef ON_PC cout << naive(a, req) << "\n"; #endif 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))]++; } vector<vector<vector<int>>> qcnt((1 << 7), vector<vector<int>>(2, vector<int>(2))); for (int w = 0; w < q; w++){ qcnt[req[w][2]][(req[w][0] <= i && i <= req[w][1])][(req[w][0] <= j && j <= req[w][1])]++; } for (int h = 0; h < (1 << 7); h++){ for (int i1 = 0; i1 <= 1; i1++){ for (int i2 = 0; i2 <= 1; i2++){ dp1 = dp0; int x = h * i1; int y = h * i2; int cnt = qcnt[h][i1][i2]; if (cnt){ for (int s = 0; s < (1 << 7); s++){ for (int k = 0; k < 7; k++){ if (y & (1 << k)){ swap(dp0[s][k][0], dp0[s][k][1]); } dp1[s ^ x][k][0] = add(dp1[s ^ x][k][0], mul(pw2[cnt - 1], dp0[s][k][0])); dp1[s ^ x][k][1] = add(dp1[s ^ x][k][1], mul(pw2[cnt - 1], dp0[s][k][1])); if (y & (1 << k)){ swap(dp0[s][k][0], dp0[s][k][1]); } dp1[s][k][0] = add(dp1[s][k][0], mul(sub(pw2[cnt - 1], 1), dp0[s][k][0])); dp1[s][k][1] = add(dp1[s][k][1], mul(sub(pw2[cnt - 1], 1), dp0[s][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)); } } } } cout << res << "\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...