202503021838 数论 矩阵乘法

通常会和 qmi 一起考, 题目背景通常是递推。

两个矩阵 $a:A\times B$ 与 $b:B\times C$ , 进行矩阵乘法后得到 $C:A\times C$ 的矩阵。 $a_i$ 的第 $i$ 行与 $b_j$ 的第 $j$ 列相乘, 为 $c_{ij}$ 的值。

for(int i = ; i <= A; i++)
	for(int j = 1; j <= C; j++)
		for(int k = 1; k <= B; k++)
			c[i][j] += a[i][k] * b[j][k];

具有结合律, $A\times B\times C=A(B\times C)$ , 但没有交换律。 因此, 在求 $A\times x\times x\times x\cdots \times x$ 时, 可以先把 $x$ 们算出来。类似于 二进制优化多重背包, 求 $S\to E$ 恰好经过 $K$ 条边中的思路。也就是快速幂的应用, 求出二进制最小元, 再组成答案。 复杂度为 $O(\log n)$

题目

题目	简介
佳佳的 Fibonacci
Fibonacci 前 n 项和