สมมติว่าเรามีตัวเลขในรูปแบบสตริง และเราต้องหาผลรวมของสตริงย่อยทั้งหมดของ s คำตอบอาจมีขนาดใหญ่มาก ดังนั้นส่งคืนผลลัพธ์ modulo 10^9+7
ดังนั้น หากอินพุตเป็น s ="268" ผลลัพธ์จะเป็น 378 เนื่องจากสตริงย่อยคือ "2", "6", "8", "26", "68" และ "268" ผลรวมทั้งหมดคือ 378 .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- M :=10^9 + 7
- sum_val :=0
- B :=1
- res :=0
- สำหรับ i ในขนาดช่วง s - 1 เหลือ 0, ลดลง 1, ทำ
- res :=(res + ค่าหลักของ s[i] * B *(i + 1)) mod M
- sum_val :=sum_val - ค่าหลักของ s[i]
- B :=(B * 10 + 1) mod M
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
