fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. // === CẤU HÌNH HASHING ===
  8. const long long MOD = 1e9+9277;
  9. const int BASE = 1e9+1;
  10. const int MAXN = 2005;  // Tăng nhẹ giới hạn N phòng trường hợp
  11.  
  12. long long POW[MAXN];
  13. long long h[MAXN];   // Hash xuôi
  14. long long rh[MAXN];  // Hash ngược (để lấy hash của đoạn đảo ngược nhanh)
  15. int n;
  16.  
  17. // Hàm lấy Hash xuôi của đoạn [l, r]
  18. long long getHash(long long hashArr[], int l, int r) {
  19.     if (l > r) return 0;
  20.     long long res = (hashArr[r] - hashArr[l - 1] * POW[r - l + 1]) % MOD;
  21.     if (res < 0) res += MOD;
  22.     return res;
  23. }
  24.  
  25. // Hàm tính Hash của dãy con [Start, End]
  26. // Trong đó đoạn con [l, r] (nằm trong Start, End) bị đảo ngược
  27. long long getHashWithReverseSub(int Start, int End, int l, int r) {
  28.     // Đoạn [Start ... End] chia làm 3 phần:
  29.     // P1: [Start ... l-1] (giữ nguyên)
  30.     // P2: [l ... r] (đảo ngược)
  31.     // P3: [r+1 ... End] (giữ nguyên)
  32.  
  33.     // 1. Hash P1
  34.     long long p1 = getHash(h, Start, l - 1);
  35.  
  36.     // 2. Hash P2 (Lấy từ mảng rh)
  37.     // Mapping: l -> n - r + 1, r -> n - l + 1
  38.     int rl = n - r + 1;
  39.     int rr = n - l + 1;
  40.     long long p2 = getHash(rh, rl, rr);
  41.  
  42.     // 3. Hash P3
  43.     long long p3 = getHash(h, r + 1, End);
  44.  
  45.     // Ghép Hash: P1 * B^(len2 + len3) + P2 * B^len3 + P3
  46.     int len2 = r - l + 1;
  47.     int len3 = End - r;
  48.  
  49.     long long res = p1;
  50.     res = (res * POW[len2 + len3]) % MOD;  // Dịch P1
  51.  
  52.     long long p2_shifted = (p2 * POW[len3]) % MOD;  // Dịch P2
  53.     res = (res + p2_shifted) % MOD;
  54.  
  55.     res = (res + p3) % MOD;  // Cộng P3
  56.  
  57.     return res;
  58. }
  59.  
  60. // Hàm đếm số dãy khác nhau tạo được từ đoạn [L, R]
  61. long long countDistinctArrays(int L, int R) {
  62.     if (L > R) return 1;  // Đoạn rỗng coi như có 1 trường hợp
  63.  
  64.     vector<long long> distinctHashes;
  65.  
  66.     // 1. Thêm trường hợp gốc (không đảo gì cả)
  67.     distinctHashes.push_back(getHash(h, L, R));
  68.  
  69.     // 2. Thử đảo mọi đoạn con [i, j] nằm trong [L, R]
  70.     // Chỉ đảo đoạn có độ dài >= 2 vì đảo độ dài 1 không thay đổi gì
  71.     for (int i = L; i <= R; i++) {
  72.         for (int j = i + 1; j <= R; j++) {
  73.             long long val = getHashWithReverseSub(L, R, i, j);
  74.             distinctHashes.push_back(val);
  75.         }
  76.     }
  77.  
  78.     // 3. Đếm số phần tử khác nhau
  79.     sort(distinctHashes.begin(), distinctHashes.end());
  80.     return unique(distinctHashes.begin(), distinctHashes.end()) - distinctHashes.begin();
  81. }
  82.  
  83. int main() {
  84.     ios_base::sync_with_stdio(false);
  85.     cin.tie(NULL);
  86.     freopen("tet.inp", "r", stdin);
  87.     freopen("tet.out", "w", stdout);
  88.  
  89.     int q;
  90.     if (!(cin >> n >> q)) return 0;
  91.  
  92.     vector<int> a(n + 1);
  93.     vector<int> ra(n + 1);
  94.  
  95.     for (int i = 1; i <= n; i++) cin >> a[i];
  96.  
  97.     // Tạo mảng đảo ngược để hỗ trợ tính toán
  98.     for (int i = 1; i <= n; i++) ra[i] = a[n - i + 1];
  99.  
  100.     // --- PRECOMPUTE HASH ---
  101.     POW[0] = 1;
  102.     for (int i = 1; i <= n; i++) POW[i] = (POW[i - 1] * BASE) % MOD;
  103.  
  104.     h[0] = 0;
  105.     for (int i = 1; i <= n; i++) h[i] = (h[i - 1] * BASE + a[i]) % MOD;
  106.  
  107.     rh[0] = 0;
  108.     for (int i = 1; i <= n; i++) rh[i] = (rh[i - 1] * BASE + ra[i]) % MOD;
  109.     // -----------------------
  110.  
  111.     while (q--) {
  112.         int P;
  113.         cin >> P;
  114.  
  115.         // Tính số lượng dãy khác nhau bên trái (1 ... P-1)
  116.         long long leftCount = countDistinctArrays(1, P - 1);
  117.  
  118.         // Tính số lượng dãy khác nhau bên phải (P+1 ... N)
  119.         long long rightCount = countDistinctArrays(P + 1, n);
  120.  
  121.         // Yêu cầu: Lấy MAX của 2 bên
  122.         cout << max(leftCount, rightCount) << "\n";
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uqv5yz
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!