两个变量的乘法随时间增加

Question

这是我练习的问题。你知道吗

有两种细菌。比如说x和y。它们每秒钟都在改变类型的同时繁殖。你知道吗

类型x变成2y类型和1x类型（x -> 2y + x）。类型y变成3x类型和1y类型（y -> 3x + y）。除此之外，1x型和3y型是自发产生的（每秒钟->；x + 3y）。你知道吗

任务是计算给定时间后细菌的数量t。你知道吗

我在这里写了一个代码：

x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x += tempX + 1 - x # spontaneous addition of 1 x bacteria
        y += tempY + 3 - y # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)

我的代码的时间复杂度在这里是O（t）。但是有什么改进的方法吗？对于小的输入是可以的。但是当我把t推到10^18，把x，y增加到1000，要花很多时间才能找到答案

Answer 1

如果我理解正确的话，x' = x+3y+1和y' = 2x+y+3。假设你的初始种群是10x和7y，你想一步一步地进化它。这可以通过以下矩阵乘法来建模：

|1 3 1|   |10|
|3 1 3| x | 7|
|0 0 1|   | 1|

为了找到答案，你需要重复矩阵乘法t次。你知道吗

不过，按照您编写代码的方式，每个x变成2y和0x，而不是2y和一个x

Answer 2

一个小小的进步。你知道吗

你把这个值加到它本身，然后减去它原来的值。你知道吗

x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x = tempX + 1 # spontaneous addition of 1 x bacteria
        y = tempY + 3 # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)