Submission #992914

#TimeUsernameProblemLanguageResultExecution timeMemory
992914danikoynovIntergalactic ship (IZhO19_xorsum)C++14
0 / 100
278 ms30188 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const ll mod = 1e9 + 7; const int maxn = 1010; const int maxbit = 7; const int maxq = 1e5 + 10; int n, q; int a[maxn]; struct query_data { int l, r, x; void input() { cin >> l >> r >> x; } } task[maxq]; bool is_affected(int i, int bit_i, int t) { if (task[t].r < i || task[t].l > i) return false; if ((task[t].x & (1 << bit_i)) == 0) return false; return true; } ll fac[maxq], inv[maxq]; ll power(ll base, ll st) { ll res = 1; while(st > 0) { if (st % 2 == 1) res = (res * base) % mod; base = (base * base) % mod; st /= 2; } return res; } ll comb(ll from, ll take) { if (take < 0 || take > from) return 0; return ((fac[from] * inv[take]) % mod * inv[from - take]) % mod; } ll pw[maxq]; bitset < 310 > bt[maxbit][maxn]; vector < int > spot[(1 << maxbit) * 2][maxn]; int ch[maxbit][maxn]; int get_both(int mask, int left, int right) { int cnt = 0; for (int i = 1; i <= left; i ++) { for (int cur : spot[mask][i]) if (cur >= right) cnt ++; } return cnt; } void solve() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; cin >> q; fac[0] = inv[0] = pw[0] = 1; for (int i = 1; i < max(q + 1, maxbit * 2); i ++) { pw[i] = (pw[i - 1] * 2) % mod; } for (int i = 1; i <= q; i ++) { fac[i] = (fac[i - 1] * (ll)(i)) % mod; inv[i] = power(fac[i], mod - 2); } for (int i = 1; i <= q; i ++) { task[i].input(); for (int bit1 = 0; bit1 < maxbit; bit1 ++) for (int bit2 = 0; bit2 < maxbit; bit2 ++) { int mask = ((1 << bit1) | (1 << bit2)); if ((task[i].x & mask) == mask) { spot[mask][task[i].l].push_back(task[i].r); } } } for (int i = 1; i <= n; i ++) { for (int bit = 0; bit < maxbit; bit ++) { for (int j = 1; j <= q; j ++) { ch[bit][i] += is_affected(i, bit, j); bt[bit][i][j] = is_affected(i, bit, j); } } } ll ans = 0; for (int i = 1; i <= n; i ++) { for (int j = i; j <= n; j ++) { for (int bit_i = 0; bit_i < maxbit; bit_i ++) { for (int bit_j = 0; bit_j < maxbit; bit_j ++) { int both = 0; int ch_i = 0; int ch_j = 0; int neit = 0; //ch_i = bt[bit_i][i].count(); //ch_j = bt[bit_j][j].count(); ch_i = ch[bit_i][i]; ch_j = ch[bit_j][j]; ///both = get_both(((1 << bit_i) | (1 << bit_j)), i, j); both = (bt[bit_i][i] & bt[bit_j][j]).count(); assert(both == get_both(((1 << bit_i) | (1 << bit_j)), i, j)); ch_i -= both; ch_j -= both; neit = q - both - ch_i - ch_j; /**for (int t = 1; t <= q; t ++) { bool af_i = is_affected(i, bit_i, t), af_j = is_affected(j, bit_j, t); if (af_i == false && af_j == false) neit ++; else if (af_i == true && af_j == false) ch_i ++; else if (af_i == false && af_j == true) ch_j ++; else if (af_i == true && af_j == true) both ++; }*/ int val_i = ((a[i] & (1 << bit_i)) > 0); int val_j = ((a[j] & (1 << bit_j)) > 0); ll res = 0; for (int d_i = 0; d_i < 2; d_i ++) for (int d_j = 0; d_j < 2; d_j ++) for (int b = 0; b < 2; b ++) { if ((val_i + d_i + b) % 2 == 0 || (val_j + d_j + b) % 2 == 0) continue; ll way_i = 0; ll way_j = 0; ll way_b = 0; for (int l = d_i; l <= ch_i; l += 2) { way_i += comb(ch_i, l); if (way_i >= mod) way_i -= mod; } for (int l = d_j; l <= ch_j; l += 2) { way_j += comb(ch_j, l); if (way_j >= mod) way_j -= mod; } for (int l = b; l <= both; l += 2) { way_b += comb(both, l); if (way_b >= mod) way_b -= mod; } ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0) { ///cout << "ways " << way_i << " " << way_j << " " << way_b << endl; } ll ways = ((way_i * way_j) % mod * way_b) % mod; res = res + ways; if (res >= mod) res -= mod; } res = (res * (pw[bit_i + bit_j])) % mod; res = (res * pw[neit]) % mod; res = (res * (ll)(i) * (ll)(n - j + 1)) % mod; if (i != j) res = (res * 2) % mod; ans += res; if (ans >= mod) ans -= mod; ///if ((a[i] & (1 << bit_i)) > 0 && (a[j] & (1 << bit_j)) > 0) { ///cout << i << " " << j << " " << bit_i << " " << bit_j << " " << res << endl; ///cout << pw[bit_i + bit_j] << " " << (i * (n - i + 1)) << endl; ///cout << ans << endl; } } } } } cout << ans << endl; } int main() { speed(); solve(); return 0; } /** 2 1 3 2 1 2 2 1 1 1 */
#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...