Pythonで時間t後のウイルス増殖数の期待値を求めるプログラム

ある危険なウイルスが急速に増殖していると仮定しましょう。このウイルスは、1単位時間ごとに細胞数がx倍になる確率が0.5、y倍になる確率も0.5となっています。最初にウイルスの細胞が1個だけ存在していたとき、時間t後に存在するウイルス細胞数の期待値を計算してください。ただし、答えが非常に大きくなる場合は、結果を10^9+7で割った余りを出力します。

例として、入力が x = 2、y = 4、t = 1 の場合を考えてみます。初期状態ではウイルスは1個の細胞しか持っていません。確率0.5でその数は2倍になり、同じく確率0.5で4倍になります。したがって、時間t = 1後のウイルス細胞数の期待値は次のように求められます。

0.5 × 2 × 1 + 0.5 × 4 × 1 = 3

この問題のポイントは、1ステップあたりの増殖倍率の期待値が (x + y) / 2 になることです。つまり、求めるべき値は ((x + y) / 2)^t となります。tが大きくなると単純な累乗計算ではコストが膨大になるため、繰り返し二乗法(バイナリ累乗法)を用いることで、O(log t) の計算量で効率的に答えを求めることができます。

解法のアルゴリズム

以下の手順に従って解きます。

• m = 10^9 + 7 を法として計算する
• factor := (x + y) // 2(1ステップあたりの増殖倍率の期待値)
• res := 1 と初期化する
• t > 0 の間、以下を繰り返す(繰り返し二乗法):
  • t が奇数の場合:res := (res * factor) mod m
  • factor := (factor * factor) mod m
  • t := t // 2
• 最後に res を返す

実装例

それでは、Pythonでの実装例を見て、動作をより深く理解しましょう。

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