Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Đếm phép gán thỏa công thức 2-SAT

    Cho công thức 2-SAT trên nnn biến x1,…,xnx_1,\dots,x_nx1​,…,xn​ gồm mmm mệnh đề, mỗi mệnh đề là tuyển của đúng hai literal. Một literal được mã hóa bằng số nguyên khác 0: +i+i+i nghĩa là xix_ixi​, −i-i−i nghĩa là ¬xi\lnot x_i¬xi​. Hãy đếm số phép gán (x1,…,xn)∈{0,1}n(x_1,\dots,x_n)\in\{0,1\}^n(x1​,…,xn​)∈{0,1}n làm cho mọi mệnh đề đều đúng.

    • Định dạng đầu vào:

      Dòng đầu: nnn, mmm. mmm dòng sau, mỗi dòng hai số nguyên khác 0 mô tả hai literal của một mệnh đề.

    • Ràng buộc đầu vào:

      1≤n≤201 \le n \le 201≤n≤20, 0≤m≤2000 \le m \le 2000≤m≤200.

    • Định dạng đầu ra:

      Một dòng: số phép gán thỏa toàn bộ công thức.

    Ví dụ:

    Đầu vào:

    2 2
1 2
-1 2

    Đầu ra:

    2

    Giải thích:

    Mệnh đề $(x_1\lor x_2)\land(\lnot x_1\lor x_2)$: chỉ thỏa khi $x_2=1$ (với $x_1$ tùy ý), nên có 2 phép gán.

    Đang tải editor...