Bình luận

• 
  

  4

  SPyofgame    9:21 a.m. 12 Tháng 6, 2020 ← chỉnh sửa 21 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Khi chọn số \(-1\) tại các vị trí (i, j) bất kì không nằm trên cột cuối và hàng cuối, ta chỉ có 1 cách để chọn hàng cuối và cột cuối

  ---

  Hint 2

  • Có \(2 ^ {n - 1}\) cách chọn dãy {0, 1} độ dài n mà số số 1 được chọn là số lẻ <=> tổng lẻ

  ---

  Hint 3

  • Có \(2 ^ {n - 1}\) cách chọn dãy {-1, 1} độ dài n mà số số -1 được chọn là số lẻ <=> tích âm

  ---

  Hint 4 (cuom1999)

  • Công thức: (2 ^ {(n - 1) * (m - 1)}

  Nếu không kể hàng cuối và cột cuối, chúng ta còn lại bảng con \((m−1) * (n−1)\).

  Có \(2 ^ {(m−1) * (n−1)}\) cách điền số cho bảng con này, do mỗi ô có 2 cách điền.

  Đồng thời với mỗi cách điền trên, chúng ta có đúng 1 cách điền số cho hàng cuối và cột cuối

  ---

  Hint 5

  • Dùng chia để trị để tính \(x ^ n\) \(\%\) \(m\) trong \(O(log_2 n)\)

  Công thức: \(x ^ n\) \(\%\) \(m = (a ^ k * a ^ k * b)\) \(\%\) \(m\)

  Với a = (x % m)

  Với k = ⌊n / 2⌋

  Với b = a (khi n lẻ)

  Với b = 1 (khi n chẵn)

  ---

  Reference AC code | O(1) time | O(1) auxiliary space | Divide and Conquer, Math

  C++

  int mulMOD(int a, int b, int m = 1e9 + 7) { return (1LL * a * b) % MOD; }
  int powMOD(int x, ll n, int m = 1e9 + 7)
  {
      int res = 1;
      for (x %= m; n > 0; x = mulMOD(x, x, m), n >>= 1)
          if (n & 1) res = mulMOD(res, x, m);
  
      return res;
  }
  
  int main()
  {
      int n = readInt();
      int m = readInt();
      cout << powMOD(2, 1LL * (n - 1) * (m - 1));
      return 0;
  }
  

• 
  

  2

  cuom1999    9:20 p.m. 12 Tháng 6, 2020

  Công thức thì đúng rồi nhưng mấy hint của em chưa rõ ràng lắm (làm sao để có được công thức). Bài này có thể giải như sau:

  Nếu không kể hàng cuối và cột cuối, chúng ta còn lại bảng con \((m-1) \times (n-1)\). Có \(2^{(m-1)(n-1)}\) cách điền số cho bảng con này, do mỗi ô có 2 cách điền. Đồng thời với mỗi cách điền trên, chúng ta có đúng 1 cách điền số cho hàng cuối và cột cuối (chứng minh nhường lại bạn đọc). Vì vậy đáp số là \(2^{(m-1)(n-1)}\).

• 
  

  2

  jumptozero    7:41 a.m. 13 Tháng 6, 2020 ← đã chỉnh sửa →

  Mình xin giải thích nốt phần "nhường lại bạn đọc" trong hướng dẫn của @cuom1999 như sau:

  • Xét một cột (hàng) bất kì trong bảng con \((m-1)(n-1)\), gọi tích các phần tử trong cột(hàng) đó là \(S\). Khi đó ta có \(S=1\) hoặc \(S=-1\).
  • Nếu \(S=1\). Thì ô thứ \(n\) của cột (hàng) đó buộc ta phải điền số \(1\) , còn nếu \(S=-1\), thì buộc ta phải điền số \(-1\).
  • Như vậy, cho dù \(S=1\) hay \(-1\) thì ta cũng chỉ có \(1\) cách điền cho ô thứ \(n\) đó.

  Vì mỗi ô chỉ có một cách điền nên với mỗi cách điền vào bảng con \((m-1)(n-1)\), chúng ta có đúng 1 cách điền số cho hàng cuối và cột cuối tương ứng . Vậy ta đã chứng minh xong phần "nhường lại bạn đọc"

• 
  

  3

  cuom1999    8:22 a.m. 13 Tháng 6, 2020

  

  Một chi tiết nhỏ là ô đặc biệt \((m, n)\) ở góc dưới bên phải. Sau khi điền hết các ô màu xanh lá cây như trên (dựa theo các ô đỏ), chúng ta phải chứng minh là ô màu xanh dương chỉ có đúng 1 cách điền. Tức là tích các ô xanh lá cây trên hàng cuối = tích các ô xanh lá cây trên cột cuối. Điều này đúng vì chúng đều bằng tích các ô đỏ.

• 
  

  1

  jumptozero    8:31 a.m. 13 Tháng 6, 2020

  @cuom1999, bài này hay quá, mình cũng quên để ý chỗ ô \((m,n)\)
• 
  

  1

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

  Vâng anh, em hiểu rồi ạ
2 bình luận nữa