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


  • -1
    long123mlj    5:34 p.m. 5 Tháng 2, 2023

    https://t.me/pump_upp - best crypto pumps on telegram
    Make 1000% and more within 1 day, join channel @pump_upp !


    • -3
      phunguyen3110    4:54 a.m. 21 Tháng 1, 2023

      https://t.me/pump_upp - best crypto pumps on telegram
      Make 1000% and more within 1 day, join channel @pump_upp !


      • 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;
}
        1 phản hồi