矩阵指数任务

Question

我有一个奇怪的问题。假设有一种疾病刚好持续 3 天，开始时有 m 名感染者。在感染的第一天，感染者感染了 d1 人，第二天感染了 d2 人，第三天感染了 d3 人，然后在第 4 天他康复了（他不再被视为生病）。任务是说第n天会有多少人被感染。

example1
n = 4, m = 2
d1 = 1, d2 = 2, d3 = 3
result = 34

example2
n = 1, m = 5
d1 = 100, d2 = 200, d3 = 5
result = 500

example3
n = 3, m = 5
d1 = 5, d2 = 5, d3 = 5
result = 900

我认为它类似于可以使用矩阵在 O(log n) 时间内计算出的斐波那契数列...

Answer 1

首先，根据您的示例，您的问题似乎是 最后一天有多少人被感染？ 而不是 有多少人患病n天后会有.

第i天的新增感染者可以通过递归计算得到：

d(0) = m
d(1) = d1 * d(0)
d(2) = d1 * d(1) + d2 * d(0)
d(i) = d1 * d(i - 1) + d2 * d(i - 2) + d3 * d(i - 3)

在这样的计算中，我们对所有被感染的新感染者求和：

昨天：d1 * d(i - 1)
前一天：d2 * d(i - 2)
2 天前：d3 * d(i - 3)

在example1中，我们可以计算：

d(0) = m = 2 , d(1) = 2, d(2) = 6, d(3) = 16
d(4) = d1 * d(3) + d2 * d(2) + d3 * d(1) = 1 * 16 + 2 * 6 + 3 * 2 = 34

示例2中：

d(1) = 100 * 5 = 500

示例 3：

d(0) = 5, d(1) = 25, d(2) = 125 + 25 = 150
d(3) = 150 * 5 + 25 * 5 + 5 * 5 = 900

Answer 2

让f(n)表示感染者的数量。我们只需要知道 f(n-2)、f(n-1) 和 f(n)，以便使用 :

的公式计算 f(n+1)

f(n+1) = d1 * f(n) + d2 * f(n-1) + d3 * f(n-2)

因为这个等式是linear recurrence, we can calculate f(n) using exponentiation by squaring and matrices。这是 Python 中使用 NumPy 的实现：

import numpy as np

def solve(n, m, d1, d2, d3):
    transform = np.array([[d1, 1, 0], [d2, 0, 1], [d3, 0, 0]], dtype='object')
    initial_state = np.array([[m, 0, 0]], dtype='object')
    final = initial_state * np.linalg.matrix_power(transform, n)
    return final[0][0]

assert solve(4, 2, 1, 2, 3) == 34
assert solve(1, 5, 100, 200, 5) == 500
assert solve(3, 5, 5, 5, 5) == 900

这个解决方案比单纯的方法更快。它的时间复杂度是O(log n)，前提是我们假设每次乘法和加法的计算成本是常数。

矩阵指数任务

Matrix exponential task

matrix

matrix-multiplication