fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define ii pair<int,int>
  4. #define nd second
  5. #define st first
  6. #define endl "\n"
  7.  
  8. using namespace std;
  9. const int MOD = 1e9 + 7;
  10. int n, k;
  11. vector<int> a, pre;
  12. vector<vector<int>> dp;
  13. vector<ii> Q;
  14. void add(int &x, int y)
  15. {
  16.     x += y;
  17.     if (x >= MOD)
  18.         x -= MOD;
  19.     if (x < 0)
  20.         x += MOD;
  21. }
  22. struct Trie{
  23.     Trie *child[2];
  24.     int sum;
  25. };
  26. struct Trie *getNode(void){
  27.     Trie *x = new Trie();
  28.     x->sum = 0;
  29.     return x;
  30. }
  31. vector<Trie*> root;
  32. void insert(int team, int XOR, int val){
  33.     Trie *x = root[team];
  34.     for (int i = 30; i >= 0; i--){
  35.         int key = (XOR >> i) & 1;
  36.         if (!x->child[key]) x->child[key] = getNode();
  37.         x = x->child[key];
  38.         add(x->sum, val);
  39.     }
  40. }
  41. signed main(){
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(0);
  44.     cin >> n >> k;
  45.     a.resize(n + 2);
  46.     pre.resize(n + 2);
  47.     dp.resize(n + 2, vector<int>(k + 2));
  48.     Q.resize(k + 2);
  49.     root.resize(k + 2);
  50.     for (int i = 0; i <= k; i++) root[i] = getNode();
  51.  
  52.     for (int i = 1; i <= n; i++) cin >> a[i], pre[i] = pre[i - 1] ^ a[i];
  53.     for (int i = 1; i <= k; i++) cin >> Q[i].st >> Q[i].nd;
  54.     insert(0, 0, 1);
  55.     for (int i = 1; i <= n; i++){
  56.         for (int j = 1; j <= min(i, k); j++){
  57.             int l = Q[j].st - 1, r = Q[j].nd;
  58.             int res = 0;
  59.             Trie *x = root[j - 1];
  60.             int bit;
  61.             for (bit = 30; bit >= 0; bit--){
  62.                 int key = (r >> bit) & 1, k = (pre[i] >> bit) & 1;
  63.                 if (key && x->child[k]) add(res, x->child[k]->sum);
  64.                 if (!x->child[key ^ k]) break;
  65.                 x = x->child[key ^ k];    
  66.             }
  67.             if (bit == -1) add(res, x->sum);
  68.             x = root[j - 1];
  69.             if (l >= 0){
  70.                 for (bit = 30; bit >= 0; bit--){
  71.                     int key = (l >> bit) & 1, k = (pre[i] >> bit) & 1;
  72.                     if (key && x->child[k]) add(res, -x->child[k]->sum);
  73.                     if (!x->child[key ^ k]) break;
  74.                     x = x->child[key ^ k];
  75.                 }
  76.                 if (bit == -1) add(res, -x->sum);
  77.             }
  78.             dp[i][j] = res;
  79.         }
  80.         for (int j = 1; j <= min(i, k); j++)
  81.             insert(j, pre[i], dp[i][j]);
  82.     }
  83.     cout << dp[n][k] << endl;
  84.  
  85. }
Success #stdin #stdout 0s 5548KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/GTt9XJ
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!