โปรแกรมหาจำนวนวิธีแบ่งสตริงไบนารีเป็น 3 ส่วนที่มีจำนวน 1 เท่ากันใน Python

โจทย์

ให้สตริงไบนารี s แบ่งเป็น 3 สตริงไม่ว่าง s1, s2, s3 ที่ s1 + s2 + s3 = s หาจำนวนวิธีแบ่งที่ทำให้จำนวนตัวอักษร '1' ใน s1, s2, s3 เท่ากันทุกคู่ คำตอบอาจใหญ่มาก ให้คืนค่า modulo 10^9+7

ตัวอย่าง: s = "11101011" ผลลัพธ์คือ 2 แบ่งได้เป็น "11 | 1010 | 11" และ "11 | 101 | 011"

วิธีแก้ปัญหา

1. นับจำนวน '1' ทั้งหมดใน s ให้เป็น count
2. ถ้า count % 3 != 0 คืนค่า 0 (แบ่งไม่ได้)
3. ถ้า count == 0 คืนค่า C(n-1, 2) % mod โดย n = len(s) (เลือกจุดตัด 2 จุดจาก n-1 ช่องว่าง)
4. หาตำแหน่งที่สะสม '1' ได้ครบ count/3 จากซ้าย (left) และจากขวา (right)
5. นับจำนวนตำแหน่งที่เป็นไปได้สำหรับจุดตัดซ้าย (ans[0]) และขวา (ans[1])
6. คืนค่า (ans[0] * ans[1]) % mod

ตัวอย่างโค้ด

from math import comb

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

s = "11101011"
print(solve(s))  # Output: 2

อินพุต / เอาต์พุต

Input: "11101011"
Output: 2