Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DHLEXP - Biểu thức logic

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dhlexp


 

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 và ((x AND y) OR z) là các 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: Vào từ thiết bị vào chuẩn: 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 (109 + 9) tương ứng với bộ dữ liệu trong file dữ liệu vào.

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 và ((x AND y) OR z) là các 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: Vào từ thiết bị vào chuẩn:

  • 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

 


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-04-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSG Duyên hải và Đồng bằng Bắc Bộ 2014

hide comments
2021-05-27 18:00:59
Tham khảo: https://vnspoj.github.io/problems/DHLEXP
2014-04-20 15:35:55 Lê Ðôn Khuê
Sorry các em, lỗi copy, anh đã sửa lại input ví dụ
2014-04-20 13:45:20 dyn
Dòng đầu là (a OR b) = 2 chứ không phải là 3(a OR b) = 2 thì phải :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.