矩阵乘法

矩阵乘法的简单实现

我们实现一个简单的两个矩阵相乘，A*B , B*C -- > A*C。

伪代码如下：

1
2
3
4
for(int i = 1;i <= A;i++)
    for(int j = 1;j <= C;j++)
        for(int k = 1;k <= B;k++)
            C[i][j] += A[i][k] * B[k][j];

矩阵乘法结合快速幂

一般来说我们矩阵会有AE^n的形式，我们E一般是两个维度都相同，根据矩阵的结合律，我们可以先根据快速幂求出E^n，在左乘A的到结果。

例如题目斐波那契

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.*;
import java.util.*;

class Main{
    public static Scanner sc = new Scanner(System.in);
    public static int[][] a = {{0,0,0},{0,0,1},{0,1,1}};
    public static int P = 10000;
    
    public static int[][] mul(int[][] a,int[][] b){
        int[][] c = new int[3][3];
        for(int i = 1;i <= 2;i++){
            for(int j = 1;j <= 2;j++){
                for(int k = 1;k <= 2;k++){
                    c[i][j] += (int)(((long) a[i][k] * b[k][j])%P);
                }
            }
        }
        return c;
    }
    
    public static int[][] qmi(int[][] a,int k){
        int[][] res = {{0,0,0},{0,1,0},{0,0,1}};
        while(k > 0){
            if((k & 1) == 1) res = mul(res,a);
            k >>= 1;
            a = mul(a,a);
        }
        return res;
    }
    public static void main(String[] args){
        int u = sc.nextInt();
        while(u != -1){
            if(u==0){
                System.out.println(0);
                u = sc.nextInt();
                continue;
            }
            int[][] res = mul(new int[][]{{0,0,0},{0,0,1},{0,0,0}},qmi(a,u));
            System.out.println(res[1][1]);
            u = sc.nextInt();
        }
    }
}