ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে। আমাদের 1 এর সমস্ত অক্ষর সহ সাবস্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে। উত্তরটি অনেক বড় হতে পারে তাই ফলাফল মোড 10^9 + 7 ফেরত দিন।
সুতরাং, যদি ইনপুট s ="1011010" এর মত হয়, তাহলে আউটপুট হবে 5 কারণ 1. চার গুণ "1" 2. একবার "11"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
m :=10^9+7
-
ফলাফল :=0
-
div :='0'
ব্যবহার করে বাইনারি স্ট্রিংকে বিভক্ত করে ভাগ করুন -
ডিভ-এ প্রতিটি x-এর জন্য করুন
-
যদি 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