Chương trình đếm số chuỗi con chỉ chứa ký tự '1' bằng Python

Cho một chuỗi nhị phân s. Ta cần tìm số lượng chuỗi con mà tất cả các ký tự đều là '1'. Kết quả có thể rất lớn nên trả về kết quả modulo 10^9 + 7.

Ví dụ, với s = "1011010", kết quả là 5 vì có: 4 chuỗi con "1" và 1 chuỗi con "11".

Thuật toán giải quyết

• m := 10^9 + 7
• result := 0
• Tách chuỗi s bằng ký tự '0' để lấy các đoạn liên tiếp của '1'.
• Với mỗi đoạn x:
  • Nếu x rỗng, bỏ qua.
  • Cộng vào result giá trị (len(x) × (len(x) + 1)) / 2 (số chuỗi con của một dãy liên tiếp độ dài n).
• Trả về result % m.

Ví dụ triển khai

def solve(s):
    m = 10**9 + 7
    result = 0
    for x in s.split('0'):
        if not x:
            continue
        result += (len(x) * (len(x) + 1)) // 2
    return result % m

s = "1011010"
print(solve(s))

Đầu vào

"1011010"

Đầu ra

5