สมมติว่าเรามีสตริงไบนารี s เราต้องหาจำนวนสตริงย่อยที่มีอักขระ 1 ตัวทั้งหมด คำตอบอาจมีขนาดใหญ่มาก ดังนั้นส่งคืนผลลัพธ์ mod 10^9 + 7
ดังนั้น หากอินพุตเป็นเหมือน s ="1011010" ผลลัพธ์จะเป็น 5 เพราะ 1. สี่คูณ "1" 2. หนึ่งครั้ง "11"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9+7
-
ผลลัพธ์ :=0
-
div :=แบ่งสตริงไบนารีโดยแยกโดยใช้ '0'
-
สำหรับแต่ละ x ใน div ทำ
-
ถ้า x ว่าง ให้ทำซ้ำต่อไป
-
ผล :=ผล + ผลหารของ (ขนาด x *(ขนาด x +1))/2
-
-
ส่งคืนผลลัพธ์ mod m
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(s):
m = 10**9+7
result = 0
for x in s.split('0'):
if not x: continue
result += (len(x)*(len(x)+1)) // 2
return result % m
s = "1011010"
print(solve(s)) อินพุต
"1011010"
ผลลัพธ์
5
