Bình luận

• 
  

  8

  SPyofgame    9:48 a.m. 15 Tháng 6, 2020 ← chỉnh sửa 2 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Vì số quá lớn, việc bignum sẽ TLE đấy 😢 tin tui đi, hướng này không tiếp cận được đâu

  Thay vào đó bạn có thể sài Hash và nó sẽ không TLE đâu UwU

  Nhưng vấn đề là bạn Hash và xử lí toán học sao là một chuyện QaQ

  ---

  Hint 2

  • Khi bạn sài Hash, xâu kí tự sẽ giảm đi thành giá trị \(x \in [0, modulo)\)

  Bạn có thể coi đây là tính \(modulo\) bignum (số lớn \(K\) cho số nhỏ \(modulo\))

  Số \(modulo\) nên lớn hơn giá trị \(C_n\) nên ta cũng sài modulo để tính \(C_n\)

  ---

  Hint 3

  • Tính modulo số lớn cho số nhỏ

  Với \(base\) là hệ của 2 số, trong trường hợp này là hệ thập phân hay \(base = 10\)

  Với \(digit_i\) là từng chữ số trong hệ \(base\) được duyệt \(i = 1 -> n\)

  Ta có \(res = (res \times base + digit_i)\) \(mod\) \(m\)

  Cẩn thận tràn số

  ---

  Hint 4

  • Trong phép toán modulo chỉ có phép cộng, trừ, nhân chứ không có phép chia

  Thay vào đó bạn có thể dùng Modular Inverse với \(\phi(modulo)\)

  Gọi \(inverse(a) \equiv a^{-1} \equiv \frac{1}{a}\) \((mod\) \(m)\)

  Việc tính toán sẽ trở thành \(C_n = \frac{(2n)!}{(n+1)! \times n!}\) \((mod\) \(m)\)

  \(\equiv (2n)! \times inverse(n + 1, m)! \times inverse(n, m)!\) \((mod\) \(m)\)

  ---

  Hint 5

  • Công thức Modular Inverse để tính \(\frac{1}{a} (mod\) \(m)\)

  Khi \((a, m)\) là cặp số nguyên tố cùng nhau ta có \(a ^ {\phi(m) - 1} \equiv a ^ {-1} (mod\) \(m)\)

  Có \((a, m)\) là cặp số nguyên tố cùng nhau khi \(gcd(a, b) = 1\)

  Ta cũng có \(gcd(a, p) = 1\) với \(p\) nguyên tố

  Đồng thời ta cũng có \(\phi(p) = p - 1\) với \(p\) nguyên tố

  Nên ta có công thức \(a ^ {m - 2} \equiv a ^ {-1}\) \((mod\) \(m)\)

  Vậy ta chọn các modulo \(m\) nguyên tố

  ---

  Hint 6

  • Sài Hash cần cẩn thận: \(A = B \Rightarrow f(A) = f(B)\) không phải là mũi tên hai chiều

  Tuy nhiên nếu \(f(A) \neq f(B) \Rightarrow A \neq B\) nên sẽ loại ngay trường hợp này

  Còn trường hợp còn lại, ta sẽ thử rất nhiều trường hơp \(f(A) ? f(B) \Rightarrow A ? B\) để nó đúng

  Hash phụ thuộc vào biến A và số modulo p. Nên ta sẽ kiểm tra nhiều trường hợp \(f(A, p) ? f(B, p)\)

  ---

  Hint 7

  • Bạn cũng có thể tiền xử lí phần giai thừa và nghịch đảo giai thừa

  Gọi các mảng sau

  \(invs[p][]\) là mảng các số nghịch đảo modulo \(p\). Có \(invs[x] \equiv x ^ {-1}\) \((mod\) \(p)\)

  \(fact[p][]\) là mảng giai thừa tự nhiên modulo \(p\). Có \(fact[x] = 1 \times 2 \times ... \times x\) \((mod\) \(p)\)

  \(tcaf[p][]\) là mảng giai thừa nghịch đảo modulo \(p\). Có \(tcaf[x] = invs[1] \times invs[2] \times ... \times invs[x]\) \((mod\) \(p)\)

  Ta có công thức:

  \(invs[p][i] \equiv invs[p][p % i] \times (p - p / i)\) \((mod\) \(p)\)

  \(fact[p][i] \equiv fact[p][i - 1] \times i\) \((mod\) \(p)\)

  \(tcaf[p][i] \equiv tcaf[p][i - 1] \times invs[i]\) \((mod\) \(p)\)

  Từ đó ta tính \(C_n\) \(mod\) \(m\)

  \(C_n = \frac{(2n)!}{(n+1)! \times n!}\) \((mod\) \(m)\)

  \(\equiv (2n)! \times invs(n + 1, m)! \times invs(n, m)!\) \((mod\) \(m)\)

  \(\equiv fact[m][2n] \times tcaf[m][n + 1] \times tcaf[m][n]\) \((mod\) \(m)\)

  ---

  Hint 8

  • Online Solving

  Ta cũng có thể không cần lưu mảng string mà cứ nhận từng kí tự là chữ số và thực hiện tính toán

  Ta có \(res = (res \times base + digit)\) \(mod\) \(m\)

  Cẩn thận tràn số

  ---

  Reference AC code | \(O(n)\) time + \(O(q)\) \(\times\) \(O(log_{10}K)\) query | \(O(n)\) auxiliary space | Online Solving, Precalculation, Query-problem, Hashing, Modular Inverse, Math, String

  C++

  vector<int> modulo = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123, 1000000181};
  
  /// Tien xu li
  vector<vector<int> > invs, fact, tcaf;
  void gen_inv(int lim = LIM)
  {
      invs = fact = tcaf = vector<vector<int> >(10, vector<int>(2, 1));
      for (int p = 0; p < 10; ++p)
      {
          int m = modulo[p];
          for (int i = 2; i <=     lim; ++i) invs[p].push_back(mulMOD(invs[p][m % i], (m - m / i), m));
          for (int i = 2; i <= 2 * lim; ++i) fact[p].push_back(mulMOD(fact[p].back(),      i     , m));
          for (int i = 2; i <=     lim; ++i) tcaf[p].push_back(mulMOD(tcaf[p].back(), invs[p][i] , m));
      }
  }
  
  /// Cong thuc tinh so Catalan
  inline int C(int n, int p) { return 1LL * fact[p][2 * n] * tcaf[p][n + 1] % modulo[p] * tcaf[p][n] % modulo[p]; }
  
  /// Kiem tra neu ki tu hien tai la chu so
  inline bool isDigit(char c) { return '0' <= c && c <= '9'; }
  
  /// Xu li truy van
  int query()
  {
      /// Input dau vao
      int n = readInt();
  
      /// Loai bo cac ki tu khong phai chu so
      char c;
      while (c = getchar(), !isDigit(c));
  
      /// Tinh res[i] = K % modulo[i]
      vector<int> res(10, 0);
      do {
          /// Duyet qua tung res[i]
          for (int i = 0; i < 10; ++i)
              res[i] = (10LL * res[i] + (c - '0')) % modulo[i]; /// Tinh toan
      } while (c = getchar(), isDigit(c)); /// Nhan chu so tiep theo
  
      /// Kiem tra
      for (int i = 0; i < 10; ++i)
          if (C(n, i) != res[i]) /// f(A) # f(B) => A # B
              return cout << "NO\n", 0;
  
      return cout << "YES\n", 0; /// f(A) = f(B) => co the A = B
  }
  

• 
  

  8

  cuom1999    10:57 a.m. 15 Tháng 6, 2020

  Có thể bổ sung thêm một ý nhỏ. Giả sử ta chọn hash với một số nguyên tố \(p\) nào đó, thì xác suất sai là \(\frac{1}{p}\) vì mỗi giá trị nhận được nằm trong đoạn \([0, p-1]\). Nếu \(p\) tầm \(10^9\), thì xác suất sai sẽ là \(10^{-9}\), đủ nhỏ để AC trên các test ngẫu nhiên, trừ khi người ra đề cố tình sinh test để diệt các mod quen thuộc như \(10^9+7\). Và nếu chúng ta chọn \(10\) số nguyên tố như trên thì xác suất sai sẽ tầm \((10^{-9})^{10} = 10^{-90}\), tuy nhiên đổi lại thuật toán sẽ chạy chậm hơn \(10\) lần.

  Vì vậy đối với các bạn hash như này, tầm \(1-3\) số nguyên tố là đủ để các bạn tự tin AC (còn nếu WA thì rất có thể thuật có sai sót). Các bạn cũng nên cẩn thận với các số nguyên tố quen thuộc như \(10^9+7\) hay \(10^9+9\) vì rất có thể người ra đề sẽ cố tình sinh test để diệt.

  p/s: CaiWinDao có tâm nên không sinh test diệt bài này :v
3 bình luận nữa