โปรแกรมหาผลรวมของซับสตริงทั้งหมดของตัวเลขที่ให้มาเป็นสตริงใน Python

สมมติว่ามีตัวเลขในรูปสตริง s ต้องหาผลรวมของซับสตริง (substring) ทุกตัวของ s คำตอบอาจใหญ่ ให้คืนค่ามอดุลลอ 10^9 + 7

ตัวอย่าง: s = "268" ผลลัพธ์ 378 เพราะซับสตริงคือ "2", "6", "8", "26", "68", "268" ผลรวม = 378

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

1. M := 10^9 + 7
2. sum_val := 0, B := 1, res := 0
3. วน i จาก len(s)-1 ลง 0:
   • res = (res + int(s[i]) * B * (i+1)) % M
   • sum_val -= int(s[i])
   • B = (B * 10 + 1) % M
4. คืนค่า res

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

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))

อินพุต

"268"

เอาต์พุต

378