Bình luận

• 
  

  0

  huyhau6a2    10:14 a.m. 5 Tháng 6, 2022

  Mem chặt quá!

• 
  

  1

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

  Editorial khá dài, hi vọng không có sai sót gì cả. Mong mọi người góp ý nếu có gì thắc mắc hay sai phạm ạ. Em cảm ơn ^^

• 
  

  9

  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
  }
  

  1 phản hồi
• 
  

  -5

  Hex    8:36 a.m. 8 Tháng 6, 2020

  Java be like:

  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

  1 phản hồi