मान लीजिए एक खतरनाक वायरस है जो तेजी से बढ़ता है। वायरस सेल्स की संख्या के फैक्टर x से बढ़ने की प्रायिकता 0.5 है और वायरस सेल्स की संख्या के फैक्टर y से बढ़ने की प्रायिकता भी 0.5 है। अब यदि शुरुआत में वायरस का एक सेल था, तो समय t के बाद वायरस सेल्स की अपेक्षित संख्या की गणना करें। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9+7 से मॉड करें।
तो, यदि इनपुट x = 2, y = 4, t = 1 है, तो आउटपुट 3 होगा, क्योंकि शुरुआत में, वायरस में केवल एक सेल है। समय x के बाद, प्रायिकता 0.5 के साथ, इसका आकार दोगुना हो जाता है (x2) और, अन्य 0.5 की प्रायिकता के साथ, इसका आकार 4 गुना बढ़ जाता है। इस प्रकार, समय t = 1 के बाद वायरस सेल की अपेक्षित संख्या है: 0.5*2*1 + 0.5*4*1 = 3।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- m = 10^9+7
- factor := floor of (x+y)/2
- res:= 1
- जब t > 0, करें
- यदि t विषम है, तो
- res :=(res*factor) mod m
- factor :=(factor*factor) mod m
- t := floor of t/2
- यदि t विषम है, तो
- res वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
m=10**9+7 def solve(x, y, t): factor=(x+y)//2 res=1 while t > 0: if t % 2: res = (res*factor) % m factor = (factor*factor) % m t = t// 2 return res x = 2 y = 4 t = 1 print(solve(x, y, t))
इनपुट
2, 4, 1
आउटपुट
3