मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है। हमें उन सबस्ट्रिंग्स की संख्या ढूंढनी है जिनके सभी वर्ण 1 हैं। उत्तर बहुत बड़ा हो सकता है इसलिए परिणाम को 10^9 + 7 से मोडुलो वापस करें।
उदाहरण के लिए, यदि इनपुट s = "1011010" है, तो आउटपुट 5 होगा क्योंकि 1. चार बार "1" 2. एक बार "11"
हल करने के चरण
m := 10^9+7
result := 0
div := बाइनरी स्ट्रिंग को '0' का उपयोग करके विभाजित करके विभाजित करें
div में प्रत्येक x के लिए, करें
यदि x खाली है, तो अगले इटरेशन के लिए जाएं
result := result + (x का आकार * (x का आकार + 1)) / 2 का भागफल
result 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