蓝桥杯算法训练奇异的虫群python实现（矩阵快速幂、快速斐波那契）

本文链接：https://blog.csdn.net/bianxia123456/article/details/106763094

这篇博客介绍了如何利用矩阵快速幂解决一个关于奇异虫群繁殖的问题。在星球上，A虫群和B虫群以特定方式繁殖，题目要求求解在给定时间t时，A虫群数量对特定模数取余的结果。通过将问题转化为快速斐波那契问题，博主详细分析了如何运用矩阵快速幂的方法来高效求解，并提供了AC代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题描述
　　在一个奇怪的星球上驻扎着两个虫群A和B，它们用奇怪的方式繁殖着，在t+1时刻A虫群的数量等于t时刻A虫群和B虫群数量之和，t+1时刻B虫群的数量等于t时刻A虫群的数量。由于星际空间的时间维度很广阔，所以t可能很大。OverMind 想知道在t时刻A虫群的数量对 p = 1,000,000,007.取余数的结果。当t=1时 A种群和B种群的数量均为1。
输入格式
　　测试数据包含一个整数t，代表繁殖的时间。
输出格式
　　输出一行，包含一个整数，表示对p取余数的结果
样例输入
10
样例输出
89
样例输入
65536
样例输出
462302286
数据规模和约定
　　对于50%的数据 t<=10^9
　　对于70%的数据 t<=10^15
　　对于100%的数据 t<=10^18

分析：

这个题目，抽象一下就是一个快速斐波那契问题， $t = 1$ 时，A虫子表示 $f (2)$ ,B虫子表示 $f (1)$ ，后面问题就是求在 $t$ 时刻A虫子的数量，就相当于是求 $f (t + 1)$ 的值。

关于斐波那契，可以直接对矩阵 $[\begin {matrix}1&1 \\1 &0\end {matrix}]$ 进行快速幂。如下：
$[\begin {matrix}1&1 \\1 &0\end {matrix}]^{n} =[\begin {matrix}f(n+1)&f(n )\\f(n)&f(n-1）\end {matrix}]$

本题目需要注意的是，后面求的是 $f (t + 1)$ 的值，所以快速幂的时候 $n = t + 1$

细节分析参考上次写的这个快速斐波那契

AC代码：

def mul_matrix(x, y):
    ans = [[0 for i in range(2)] for j in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ans[i][j] += x[i][k] * y[k][j] % mod
        ans[i][j] %= mod
    return ans


def quick_matrix(m, n, mod):
    e = [[1, 0], [0, 1]]  # 单位矩阵
    while (n):
        if n % 2 != 0:
            e = mul_matrix(e, m)
        m = mul_matrix(m, m)
        n >>= 1
    return e


t = int(input())
mod = 1000000007
print(quick_matrix([[1, 1], [1, 0]], t+1, mod)[0][1])