Bài toán yêu cầu xử lý giá trị trong phạm vi [0, 2^n) khi thực hiện các thao tác với người giàu. Trước hết xem xét trường hợp B = 20, nơi dữ liệu được xử lý dưới dạng nhị phân.

Cấu trúc 01-trie trong khoảng [0, 2^n) là giải pháp hiệu quả. Khi giá trị dị biến toàn cục là 0, phạm vi [0, y] có thể phân tách thành tối đa n cây nhị phân con đầy đủ. Nếu giá trị dị biến v khác 0, số lượng cây con không thay đổi nhưng thứ tự truy cập nhánh tại mỗi tầng bị ảnh hưởng.

Đối với B = 5/6/7, cần áp dụng trie nén bằng cách phân tách các tầng thành khối. Xác định chuỗi tỉ lệ khối c_1, c_2, ..., c_B (với ∑c_i = 20). Khối đầu tiên chứa 1 nút, mỗi nút ở khối i sẽ có 2^{c_i} nút con ở khối i+1.

Chi phí bộ nhớ được tính bằng công thức:

f(c_i) = 1 + 2∑_{k=0}^{c_i-1}4^k - 2^{c_i}

Tổng chi phí: ∑_{i=1}^B(2^{∑_{j=1}^{i-1}c_j} × f(c_i))

Sử dụng quy hoạch động với dp[i][j] biểu thị chi phí tối thiểu khi chọn i khối đầu với tổng j tầng. Kết quả tối ưu:

• B=5: [9,5,3,2,1]
• B=6: [8,5,3,2,1,1]
• B=7: [8,4,3,2,1,1,1]

Mã khởi tạo trie nén:

#include <bits/stdc++.h>

void khoiTao(int B) {
  std::vector<int> c_khoi;
  switch(B) {
    case 5: c_khoi = {9,5,3,2,1}; break;
    case 6: c_khoi = {8,5,3,2,1,1}; break;
    case 7: c_khoi = {8,4,3,2,1,1,1}; break;
  }

  std::unordered_map<uint64_t, int> bangHash;
  std::vector<std::vector<int>> cayCon(MAX_NUT);

  for(auto s : c_khoi) {
    std::vector<std::pair<uint64_t, int>> mangMoi;
    for(int i=0; i<cayCon.size(); i+=(1<<s)) {
      uint64_t hashCha = 0;
      std::vector<uint64_t> tapHash;
      for(int j=0; j<(1<<s); j++) {
        int nut = cayCon[i][j];
        hashCha ^= hash[nut];
        tapHash.push_back(hash[nut]);
      }
      cayConMoi.push_back({tapHash});
      bangHash[hashCha] = taoNutMoi();
    }
    cayCon = mangMoi;
  }
}

Hàm truy vấn:

std::vector<int> timNut(int y, int dich) {
  std::vector<int> ketQua;
  int phepXor = dich;
  int bitPos = 0;

  for(auto s : c_khoi) {
    int khoaBit = (dich >> bitPos) & ((1<<s)-1);
    int gioiHan = (y >> bitPos) & ((1<<s)-1);
    
    if(gioiHan > 0) {
      uint64_t hashTap = 0;
      for(int i=0; i<gioiHan; i++) {
        int nut = cayCon[phepXor][i ^ khoaBit];
        hashTap ^= hash[nut];
      }
      ketQua.push_back(bangHash[hashTap]);
    }
    bitPos += s;
  }
  return ketQua;
}