hackercupai/hackercup

1#include <algorithm>2#include <iostream>3#include <vector>4using namespace std;5 6const int kBitCount = 22;7 8class PersistentTrie {9  vector<int> roots, last, last_rec;10  vector<vector<int>> nodes;11 12  inline int get_root(int ind) {13    return ind == -1 ? 0 : roots[ind];14  }15 16  vector<int> get_bits(int val) {17    vector<int> bits(kBitCount, 0);18    for (int i = 0; i < kBitCount; i++) {19      if (val & (1 << i)) {20        bits[kBitCount - i - 1] = 1;21      }22    }23    return bits;24  }25 26 public:27  void reset(int n) {28    last.assign(1, -1);29    last_rec.assign(1, -1);30    nodes.assign(2, vector<int>(1, -1));31    roots.clear();32    roots.reserve(n + 1);33    last.reserve((n + 1) * (kBitCount + 1));34    last_rec.reserve((n + 1) * (kBitCount + 1));35    nodes[0].reserve((n + 1) * (kBitCount + 1));36    nodes[1].reserve((n + 1) * (kBitCount + 1));37  }38 39  void add(int val, int ind) {40    vector<int> bits = get_bits(val);41    int r = roots.size(), node_id = nodes[0].size();42    roots.push_back(node_id);43    int root_id = get_root(r - 1);44    nodes[0].push_back(nodes[0][root_id]);45    nodes[1].push_back(nodes[1][root_id]);46    last.push_back(ind);47    vector<int> visited_nodes(1, node_id);48    visited_nodes.reserve(kBitCount + 1);49    for (int i = 0; i < kBitCount; ++i) {50      int next_node_id = nodes[bits[i]][node_id];51      if (next_node_id == -1) {52        nodes[0].push_back(-1);53        nodes[1].push_back(-1);54      } else {55        nodes[0].push_back(nodes[0][next_node_id]);56        nodes[1].push_back(nodes[1][next_node_id]);57      }58      last.push_back(ind);59      next_node_id = (int)nodes[0].size() - 1;60      nodes[bits[i]][node_id] = next_node_id;61      node_id = next_node_id;62      visited_nodes.push_back(node_id);63    }64    last_rec.resize(last.size());65    last_rec[visited_nodes.back()] = last[visited_nodes.back()];66    for (int i = (int)visited_nodes.size() - 2; i >= 0; i--) {67      const int node_id = visited_nodes[i];68      last_rec[node_id] = last[node_id];69      for (int j = 0; j < 2; ++j) {70        const int child_node_id = nodes[j][node_id];71        if (child_node_id == -1) {72          last_rec[node_id] = -1;73        } else {74          last_rec[node_id] = min(last_rec[node_id], last_rec[child_node_id]);75        }76      }77    }78  }79 80  int get_mex(int l, int r, int val) {81    if (!r) {82      return val ? 0 : 1;83    }84    int res = 0;85    vector<int> bits = get_bits(val);86    int node_id = get_root(r);87    for (int i = 0; i < kBitCount; ++i) {88      if (node_id == -1) {89        break;90      }91      for (int j = 0; j < 2; ++j) {92        const int bit_val = bits[i] ^ j;93        const int child_node_id = nodes[bit_val][node_id];94        if (child_node_id == -1) {95          node_id = child_node_id;96          res |= (j << (kBitCount - i - 1));97          break;98        }99        if (last_rec[child_node_id] < l) {100          node_id = child_node_id;101          res |= (j << (kBitCount - i - 1));102          break;103        }104      }105    }106    return res;107  }108};109 110PersistentTrie trie;111 112long long solve() {113  int N, x1, y1, z1, x2, y2, z2, x3, y3, z3;114  cin >> N >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> x3 >> y3 >> z3;115  vector<int> A(N), B(N), C(N);116  long long pa = 0LL, pb = 0LL, pc = 0LL;117  for (int i = 0; i < N; i++) {118    pa = (pa * x1 + y1) % z1;119    pb = (pb * x2 + y2) % z2;120    pc = (pc * x3 + y3) % z3;121    A[i] = min(i + 1, (int)(1 + pa));122    B[i] = max(A[i], (int)(i + 1 - pb));123    C[i] = min(i, (int)pc);124  }125  A.insert(A.begin(), 0);126  B.insert(B.begin(), 0);127  C.insert(C.begin(), 0);128  trie.reset(N);129  trie.add(0, 0);130  vector<int> f(N + 1, 0);131  for (int i = 1; i <= N; ++i) {132    f[i] = trie.get_mex(i - B[i], i - A[i], f[C[i]]);133    trie.add(f[i], i);134  }135  vector<int> lnk(1 << kBitCount, -1);136  long long ans = 0LL;137  for (int i = 1; i <= N; i++) {138    if (lnk[f[i]] == -1) {139      lnk[f[i]] = i;140    }141    ans += lnk[f[i]];142  }143  return ans;144}145 146int main() {147  int T;148  cin >> T;149  for (int t = 1; t <= T; t++) {150    cout << "Case #" << t << ": " << solve() << endl;151  }152  return 0;153}154