Python程式：計算病毒在t時間後的預期增長

假設存在一種危險的病毒，其增長速度很快。病毒細胞數量增長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((x+y)/2)
  • res := 1
  • 當 t > 0 時，執行以下操作：
    • 如果t是奇數，則
      • res := (res * factor) % m
    • factor := (factor * factor) % m
    • t := floor(t/2)
  • 返回 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

更新於：2021年10月25日

瀏覽量：150

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告