BOOL - Biểu thức Boolean
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

An rất thích thú với toán học và cậu ta nhận ra rằng giá trị của một biểu thức boolean có giá trị thay đổi phụ thuộc vào thứ tự thực hiện các phép toán của nó. Để dễ hình dung, hay xem xét ví dụ sau:

Biểu thức: 1 xor 1 and 0

An có thể thực hiện biểu thức trên theo 2 thức tự khác nhau:

1. ((1 xor 1) and 0) = (0 and 0) = 0

2. (1 xor (1 and 0)) = (1 xor 0) = 1

Nhưng vì không có sự khác nhau về độ ưu tiên giữa các phép toán nên kết quả của biểu thức phụ thuộc vào cách đặt các cặp ngoặc để nhóm các hạng tử lại với nhau. Và An muốn biết rằng với một biểu thức con từ L đến R trong biểu thức S cho trước, có bao nhiêu cách biểu diễn biểu thức con đó để có kết quả thu được là   res - res bằng true hoặc false. Hai cách biểu diễn được gọi là khác nhau nếu như cách đặt các cặp ngoặc là khác nhau.

Dữ liệu nhập: gồm nhiều dòng

 - Dòng thứ nhất chứa 2 chuỗi S và T (1 ≤ |S| ≤ 300, |T| = |S| - 1). Chuỗi S biểu diễn giá trị của các hạng tử trong biểu thức (0 hoặc 1). Chuỗi T chỉ gồm các kí tự 'a', 'o' và 'x' tương ứng với and, or và xor, biểu diễn các phép toán nối giữa các hạng tử, Ti là phép toán nối giữa Si và Si+1.

 - Dòng thứ 2 chứa một số nguyên q (1 ≤ q ≤ 90000) - số lượng truy vấn

 - q dòng tiếp theo, mỗi dòng chứa 2  số nguyên L, R và chuỗi res (1 ≤ L ≤ R ≤ |S|, res bằng "true" hoặc "false")

Dữ liệu xuất: với mỗi truy vấn xuất ra trên 1 dòng là số cách biểu diễn biểu thức con [L, ,R] sao cho kết quả của nó là res. Vì số cách thu được có thể rất lớn nên chỉ cần xuất ra phần dư của kết quả thu được cho 1000000009 (109+9)

Ví dụ

  • input
    110 ax
    3
    1 1 true
    1 2 false
    2 3 false
    output
    1
    0
    0

    

Back to Top