Gợi ý ý tưởng cho bài tập đếm số dãy ngoặc bậc k

[Wipad]

Biểu thức ngoặc là xâu chỉ gồm các ký tự ‘(’ hoặc ‘)’. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng 0,
• Nếu A là biểu thức ngoặc đúng có bậc bằng 𝑘 thì (A) cũng là một biểu thức ngoặc đúng có bậc bằng 𝑘 + 1,
• Nếu A và B là hai biểu thức ngoặc đúng và có bậc tương ứng là 𝑘1 và 𝑘2 thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(𝑘1, 𝑘2).
• Ví dụ, ‘()(())’ là một biểu thức ngoặc đúng có bậc bằng 2 còn ‘(()(()))’ là một biểu thức ngoặc đúng và có bậc bằng 3.

Yêu cầu: Cho S là một xâu chỉ gồm các ký tự ‘(‘, ‘)’ và số nguyên dương 𝑘, hãy đếm số xâu con khác nhau của S (xâu nhận được từ S bằng cách giữ nguyên xóa đi một số ký tự) là biểu thức ngoặc bậc 𝑘.
Input:

• Dòng 1: xâu S có độ dài không vượt quá 1000 chỉ gồm các ký tự ‘(‘, ‘)’
• Dòng 2: số nguyên dương 𝑘 (1 ≤ 𝑘 ≤ 𝑙𝑒𝑛𝑔𝑡ℎ(𝑆) 𝑑𝑖𝑣 2).

Output: Ghi số lượng xâu con khác nhau của S là biểu thức ngoặc bậc 𝑘 chia dư cho 111539786
Ví dụ:

Input 1:

()()
1

Output 1:

2

Input 2:

((()))
2

Output 2:

1

Ràng buộc

• Subtask 1: s.length() <= 20
• Subtask 2: Không có bất cứ ràng buộc nào.

Chào mọi người, nhờ mọi người gợi ý cho em câu này với, em chưa biết làm như nào cả, em cảm ơn mọi người.

[tntxtnt]

s.\text{length} \le 20 thì cứ sinh hết 2^{20} chuỗi con từ s là được. Ví dụ s =``()()" thì có 2^4 chuỗi con tạo ra từ 0-15 số ở hệ nhị phân là 0000, 0001, 0010, 0011, 0100, \dots, 1110, 1111 (bỏ chuỗi này vì nó = s) với \color{red}0\color{green}11\color{red}0 là \color{red}(\color{green})(\color{red}) tức là chuỗi ``)("