Chương trình tìm số cách tách chuỗi nhị phân thành 3 phần có số '1' bằng nhau trong Python

Cho chuỗi nhị phân s, ta cần tách s thành 3 chuỗi con không rỗng s1, s2, s3 sao cho s1 + s2 + s3 = s. Tìm số cách tách sao cho số ký tự '1' trong s1, s2, s3 bằng nhau. Kết quả lấy modulo 10^9+7.

Ví dụ: s = "11101011" cho kết quả 2, vì có thể tách thành "11 | 1010 | 11" và "11 | 101 | 011".

Các bước giải:

• count := số lượng '1' trong s.
• m := 10^9 + 7.
• ans := mảng kích thước 2 khởi tạo 0.
• Nếu count % 3 != 0: trả về 0.
• Ngược lại nếu count == 0: trả về C(n-1, 2) % m (tổ hợp chọn 2 vị trí cắt từ n-1 khoảng trống).
• left := 0, right := len(s) - 1.
• cum_s := 0, cum_e := 0.
• Trong khi cum_s <= count//3 hoặc cum_e <= count//3:
  • Nếu s[left] == '1': cum_s += 1.
  • Nếu s[right] == '1': cum_e += 1.
  • Nếu cum_s == count//3: ans[0] += 1.
  • Nếu cum_e == count//3: ans[1] += 1.
  • left += 1, right -= 1.
• Trả về (ans[0] * ans[1]) % m.

Ví dụ minh họa

def solve(s): 
    count = s.count("1") 
    m = 10**9 + 7 
    ans = [0, 0] 
    if count % 3 != 0: 
        return 0 
    elif count == 0: 
        from math import comb 
        return comb(len(s)-1, 2) % m 
    left = 0 
    right = len(s)-1 
    cum_s = 0 
    cum_e = 0 
    while cum_s <= count//3 or cum_e <= count//3: 
        if s[left] == "1": 
            cum_s += 1 
        if s[right] == "1": 
            cum_e += 1 
        if cum_s == count//3: 
            ans[0] += 1 
        if cum_e == count//3: 
            ans[1] += 1 
        left += 1 
        right -= 1 
    return (ans[0] * ans[1]) % m  s = "11101011" 
print(solve(s))

Đầu vào

"11101011"

Đầu ra

2