123Code...

Nội dung Bài tập

Mã:: BRACKET

Tên:: Dãy ngoặc kì diệu

Dạng thi:: oi

Thang điểm:: 7 điểm

Giới hạn thời gian:: 2 giây

Giới hạn bộ nhớ:: 256 MB

Nguồn bài tập:: VNOI Online 2018

Được tạo bởi:: phuc

: Share

Vị trí mở ngoặc	Vị trí đóng ngoặc
1 2 3 7	6 5 4 8

BRACKET.INP	BRACKET.OUT
6 1 1 2	2

BRACKET.INP	BRACKET.OUT
135 0	0

BRACKET.INP	BRACKET.OUT
12 2 1 6 7 12	4

Xâu ký tự X gồm các kí tự " ( " và " ) " được coi là một dãy ngoặc đúng, khi và chỉ khi thỏa mãn một trong ba điều kiện sau: ● X là dãy rỗng; ● X = ( A ) , với A là dãy ngoặc đúng; ● X = AB, với A và B là hai dãy ngoặc đúng. Xét dãy ngoặc đúng X , kí tự đóng ngoặc ở vị trí j được gọi là tương ứng với kí tự mở ngoặc ở vị trí i, khi và chỉ khi cả ba điều kiện sau được thỏa mãn: ● i < j ; ● X [ i .. j ] là dãy ngoặc đúng; ● i + 1 > j - 1 hoặc X [ i + 1 .. j - 1] là dãy ngoặc đúng. Ở đây, kí hiệu X [ i .. j ] là xâu con bắt đầu ở vị trí i và kết thúc tại vị trí j của xâu X . Có thể chứng minh rằng, trong dãy ngoặc đúng, mỗi mở ngoặc có một và chỉ một đóng ngoặc tương ứng. Xét dãy ngoặc ((()))() , ta dễ dàng nhận thấy điều sau: Vị trí mở ngoặc Vị trí đóng ngoặc 1 2 3 7 6 5 4 8 Đếm số dãy ngoặc đúng độ dài n , thoả mãn m điều kiện. Điều kiện thứ i được cho bởi cặp số (x_i, y_i) với ý nghĩa là: ● Vị trí thứ x_i của dãy ngoặc phải là mở ngoặc; ● Vị trí thứ y_i của dãy ngoặc phải là đóng ngoặc tương ứng của mở ngoặc ở vị trí x_i Dữ liệu: Dòng đầu tiên gồm hai số nguyên dương n và m (1 ≤ n, m ≤ 10⁶ ); m dòng sau, mỗi dòng gồm hai số nguyên dương x i và y i (1 ≤ x i ≤ y i ≤ n ). Kết quả ● In ra phần dư khi chia số lượng dãy ngoặc thỏa mãn cho 10⁹ +7. Ví dụ 1: BRACKET.INP BRACKET.OUT 6 1 1 2 2 Giải thích: Hai dãy ngoặc thỏa mãn đề bài là ()()(), ()(()) . Dãy ngoặc ((())) cũng là một dãy ngoặc đúng độ dài 6, nhưng không thỏa mãn đề bài vì đóng ngoặc tương ứng của mở ngoặc ở vị trí 1 nằm ở vị trí thứ 6. Ví dụ 2: BRACKET.INP BRACKET.OUT 135 0 0 Giải thích:Rõ ràng không có dãy ngoặc đúng nào độ dài lẻ. Ví dụ 3: BRACKET.INP BRACKET.OUT 12 2 1 6 7 12 4 Giải thích: Bốn dãy ngoặc thỏa mãn đề bài là (()())(()()) , (()())((())) , ((()))(()()) , ((()))((())) . Chấm điểm ● Subtask 1 (20% số điểm): 1 ≤ n ≤ 20; ● Subtask 2 (30% số điểm): 1 ≤ n ≤ 200; ● Subtask 3 (30% số điểm): 1 ≤ n ≤ 5000; ● Subtask 4 (20% số điểm): không có ràng buộc gì thêm.
Quảng cáo