Pythonで時間t後に予想されるウイルスの増殖を見つけるプログラム

危険なウイルスがあり、それが急速に増殖するとします。ウイルス細胞の数がx倍に成長する確率は0.5であり、ウイルス細胞の数がy倍に成長する確率も0.5です。ここで、最初にウイルスのセルが1つあった場合は、t時間後に予想されるウイルスセルの数を計算します。答えが大きすぎる場合は、modの結果は10 ^ 9+7になります。

したがって、入力がx =2、y =4、t =1の場合、最初はウイルスにセルが1つしかないため、出力は3になります。 x時間後、確率0.5で、そのサイズは2倍（x2）になり、他の0.5の確率で、そのサイズは4倍になります。したがって、時間t =1以降の予想されるウイルス細胞数は、0.5 * 2 * 1 + 0.5 * 4 * 1=3です。

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7
• factor：=（x + y）/2のフロア
• res：=1
• t> 0の間、do
  • tが奇数の場合、
    • res：=（res * factor）mod m
  • factor：=（factor * factor）mod m
  • t：=t/2のフロア
• return 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