Board

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho bảng kích thước \(n \times m\). Hỏi có bao nhiêu cách điền các số \(-1\) và \(1\) vào các ô trong bảng sao cho tích các số trong cùng \(1\) hàng và trong cùng \(1\) một cột bằng \(1\).

Input

  • Một dòng chứa 2 số \(n, m\) (\(n, m \leq 10^9\))

Output

  • In ra kết quả theo mod \(10^9+7\)

Example

Test 1

Input 
2 3
Output 
4

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