Chương trình tính tổng tất cả các chuỗi con của một số cho dưới dạng chuỗi trong Python

Mô tả bài toán

Cho một số dưới dạng chuỗi s. Hãy tìm tổng của tất cả các chuỗi con của s. Kết quả có thể rất lớn, trả về modulo 10^9 + 7.

Ví dụ

Nếu đầu vào là s = "268", thì đầu ra sẽ là 378 vì các chuỗi con là "2", "6", "8", "26", "68", "268", tổng = 2+6+8+26+68+268 = 378.

Giải thuật

1. Khởi tạo M = 10^9 + 7, sum_val = 0, B = 1, res = 0.
2. Duyệt i từ len(s)-1 xuống 0:
   • res = (res + int(s[i]) * B * (i + 1)) % M
   • sum_val -= int(s[i])
   • B = (B * 10 + 1) % M
3. Trả về res.

Triển khai Python

def solve(s):
    M = 10**9 + 7
    sum_val = 0
    B = 1
    res = 0
    for i in range(len(s) - 1, -1, -1):
        res = (res + int(s[i]) * B * (i + 1)) % M
        sum_val -= int(s[i])
        B = (B * 10 + 1) % M
    return res

s = "268"
print(solve(s))

Đầu vào

"268"

Đầu ra

378