DHLEXP - Biểu thức logic
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một biểu thức logic là biểu thức gồm các biến (được kí hiệu bằng các chữ cái in thường nhận giá trị là số nguyên 32 bit không dấu) với các toán tử logic AND, OR, XOR và các dấu ngoặc. Một biểu thức hợp lệ được định nghĩa như sau:
- Nếu x, y là biến thì: x là biểu thức hợp lệ; y là biểu thức hợp lệ; (x AND y), (x OR y), (x XOR y) là các biểu thức hợp lệ.
- Nếu A, B là biểu thức hợp lệ thì: (A AND B), (A OR B), (A XOR B) là các biểu thức hợp lệ.
Ví dụ:
- x là biểu thức hợp lệ;
- ((x AND y) OR z) là biểu thức hợp lệ;
- (x AND y là biểu thức không hợp lệ vì thiếu dấu ngoặc đóng;
- (x AND y) OR z là biểu thức không hợp lệ vì thiếu cặp dấu ngoặc bao ở ngoài cùng.
Trong bài toán này chỉ xét biểu thức hợp lệ mà mỗi biến chỉ xuất hiện một lần.
Yêu cầu:
Cho một phương trình có dạng "biểu_ thức_F = P0" trong đó P0 là một số nguyên 32 bit không dấu. Hãy đếm số các bộ giá trị của các biến để khi thay vào biểu_ thức_F, ta thu được một đẳng thức đúng.
Dữ liệu:
- Dòng đầu tiên ghi số nguyên dương K là số lượng bộ dữ liệu.
- Tiếp đến là K dòng, mỗi dòng (tương ứng với một bộ dữ liệu) chứa một xâu có dạng "biểu_thức_F = P0" trong đó biểu_thức_F là một biểu thức hợp lệ.
Kết quả:
Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là phần dư của phép chia số lượng các bộ giá trị để phương trình đúng cho 1000000009 (10^9 + 9) tương ứng với bộ dữ liệu trong file dữ liệu vào.
- Subtask 1 (15/70 điểm): Giả thiết là biểu thức chỉ chứa phép OR, số lượng biến không vượt quá 8 và 0 ≤ P0 < 8
- Subtask 2 (20/70 điểm): Giả thiết là biểu thức chỉ chứa phép OR, số lượng biến không vượt quá 26 và 0 ≤ P0 < 8.
- Subtask 3 (15/70 điểm): Giả thiết là số lượng biến không vượt quá 26 và biểu thức chỉ chứa toàn phép AND hoặc biểu thức chỉ chứa toàn phép XOR.
- Subtask 4 (20/70 điểm): Giả thiết là số lượng biến không vượt quá 26 và 0 ≤ P0 < 2^32.
Ví dụ:
Dữ liệu 3 (a OR b) = 2 (a OR (b OR c)) = 3 (x XOR y) = 2 Kết quả 3 49 294967260
- Người up: beo_chay_so
- Nguồn bài: HSG Duyên hải và Ðồng bằng Bắc Bộ 2014