2024蓝桥杯每日一题（矩阵乘法）

备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一：斐波那契
        试题二：垒筛子
        试题三：斐波那契数列前n项和
        试题四：牛站

---

试题一：斐波那契

【题目描述】

        在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)给定整数 n，求Fibnmod10000。

【输入格式】

        输入包含不超过 100 组测试用例。

        每个测试用例占一行，包含一个整数 n。

        当输入用例 n=−1时，表示输入终止，且该用例无需处理。

【输出格式】

        每个测试用例输出一个整数表示结果。

        每个结果占一行。

【数据范围】

        0≤n≤2×109

【输入样例】

0
9
999999999
1000000000
-1

【输出样例】

0
34
626
6875

【解题思路】

        【f2，f3】 = 【[0，1]，[1，1]】*【f1，f2】，也就是【fn，fn-1】 = A^n【f0，f1】

【Python程序代码】

def matrix_mul(A,B,MOD):
    res = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] = (res[i][j] +A[i][k]*B[k][j])%MOD
    return res
def fib(k):
    ans = [[0,1],[0,0]]
    mat = [[0, 1], [1, 1]]
    while k>0:
        if k&1==1:
            ans = matrix_mul(ans,mat,10000)
        k = k>>1
        mat = matrix_mul(mat,mat,10000)
    return ans[0][0]
while True:
    n = int(input())
    if n==-1:break
    if n==0:print(0)
    elif n==1:print(1)
    else:
        print(fib(n))

---

试题二：垒筛子

【题目描述】

        赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。由于方案数可能过多，请输出模 109+7的结果。

【输入格式】

        第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。

        接下来 m 行，每行两个整数 a,b，表示 a 和 b 数字不能紧贴在一起。

【输出格式】

        共一个数，表示答案模 109+7 的结果。

【数据范围】

        1≤n≤109
        1≤m≤361
        1≤a,b≤6

【输入样例】

2 1
1 2

【输出样例】

544

【解题思路】

        状态转移 f[i][j] = f[i - 1][k] * 4 ，肯定是会爆的，考虑如何变成矩阵乘法的形式。构建状态转移矩阵，A，当x,y不能放一块时置为0，能放一块时置为4.

【Python程序代码】

n,m = map(int,input().split())
a = [[4]*6 for i in range(6)]
p = 10**9+7
def get_op(x):
    if x<3:return x+3
    else:return x-3
for i in range(m):
    x,y = map(int,input().split())
    x,y =x-1,y-1
    a[x][get_op(y)]=0
    a[y][get_op(x)]=0
f = [[0]*6 for i in range(6)]
f[0]=[4,4,4,4,4,4]
k = n-1
def matrix_mul(a,b):
    c = [[0]*6 for i in range(6)]
    for i in range(6):
        for j in range(6):
            for k in range(6):
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % p
    return c
while k:
    if k&1:f = matrix_mul(f,a)
    a = matrix_mul(a,a)
    k>>=1
res = 0
for i in range(6):
    res = (res+f[0][i])%p
print(res)

---

试题三：斐波那契前 n 项和

【题目描述】

【解题思路】

        构建状态转移矩阵 a = [[0,1,0],[1,1,1],[0,0,1]]，F（f2,f3,s2） = a*F（f1,f2,s1） 

【Python程序代码】

n,m = map(int,input().split())
f = [[0]*3 for i in range(3)]
f[0] = [1,1,1]
a = [[0,1,0],[1,1,1],[0,0,1]]
def matrix_mul(a,b):
    c = [[0]*3 for i in range(3)]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                c[i][j] = (c[i][j]+a[i][k]*b[k][j])%m
    return c
k = n-1
while k:
    if k&1:f=matrix_mul(f,a)
    a = matrix_mul(a,a)
    k>>=1
print(f[0][2])

---

试题四：牛站

【题目描述】

        给定一张由 T 条边构成的无向图，点的编号为 1∼1000 之间的整数。求从起点 S 到终点 E 恰好经过 N 条边（可以重复经过）的最短路。注意: 数据保证一定有解。

【输入格式】

        第 1 行：包含四个整数 N，T，S，E。

        第 2..T 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

【输出格式】

        输出一个整数，表示最短路的长度。

【数据范围】

        2≤T≤100
        2≤N≤106

【输入数据】

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

【输出数据】

10

【解题思路】

        类Floyd算法+qmi，参考AcWing 345. 牛站矩阵做法详解(类Floyd算法) - AcWing

【Python代码】

n,t,s,e = map(int,input().split())
cnt = 0
d = dict()
d[s] = cnt; cnt+=1
s = d[s]
d[e] = cnt; cnt+=1
e = d[e]
g = [[0x3f3f3f3f]*(210) for _ in range(210)]
for i in range(t):
    c,a,b = map(int,input().split())
    if a not in d:
        d[a]=cnt; cnt+=1
    if b not in d:
        d[b]=cnt; cnt+=1
    a,b = d[a],d[b]
    g[a][b]=g[b][a] = min(g[a][b],c)
def work(a,b):
    temp = [[0x3f3f3f3f]*(cnt+5) for _ in range(cnt+5)]
    for i in range(cnt):
        for j in range(cnt):
            for k in range(cnt):
                temp[i][j] = min(temp[i][j],a[i][k]+b[k][j])
    return temp
res = [[0x3f3f3f3f]*(cnt+5) for _ in range(cnt+5)]
for i in range(cnt):res[i][i]=0
while n:
    if n&1:
        res = work(res,g)
    g = work(g,g)
    n>>=1
print(res[s][e])