Giả sử chúng ta có một số ở định dạng chuỗi và chúng ta phải tìm tổng của tất cả các chuỗi con của s. Câu trả lời có thể rất lớn, vì vậy, kết quả trả về modulo 10 ^ 9 + 7.
Vì vậy, 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" và "268" tổng tổng là 378 .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- M:=10 ^ 9 + 7
- sum_val:=0
- B:=1
- res:=0
- đối với tôi trong phạm vi kích thước s - 1 giảm xuống 0, giảm 1, thực hiện
- res:=(res + giá trị chữ số của s [i] * B * (i + 1)) mod M
- sum_val:=sum_val - giá trị chữ số của s [i]
- B:=(B * 10 + 1) mod M
- trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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