P3390 【模板】矩阵快速幂

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Mat {
    int mat[MAXmat][MAXmat];
    Mat() {
        memset(mat, 0, sizeof(mat));
    }
    Mat(int a[MAXmat][MAXmat]) {
        for (re int i = 0; i < MAXmat; ++i) {
            for (re int j = 0; j < MAXmat; ++j) {
                mat[i][j] = a[i][j];
            }
        }
    }
    inline void operator=(Mat x) {
        for (re int i = 0; i < MAXmat; ++i) {
            for (re int j = 0; j < MAXmat; ++j) {
                mat[i][j] = x.mat[i][j];
            }
        }
    }
    inline Mat operator+(Mat x) {
        Mat ans;
        for (int i = 0; i < MAXmat; ++i) {
            for (int j = 0; j < MAXmat; ++j) {
                ans.mat[i][j] = (mat[i][j] + x.mat[i][j]) % MOD;
            }	
        }
        return ans;
    }
    inline Mat operator*(Mat x) {
        Mat ans;
        for (re int i = 0; i < MAXmat; ++i) {
            for (re int k = 0; k < MAXmat; ++k) {
                int a = mat[i][k];
                for (re int j = 0; j < MAXmat; ++j) {
                    ans.mat[i][j] = (a * x.mat[k][j] + ans.mat[i][j]) % MOD;
                }
            }
        }
        return ans;
    }
    inline Mat operator^(int x) {
        Mat ans, base;
        for (re int i = 0; i < MAXmat; ++i) {
            ans.mat[i][i] = 1;
        }
        for (re int i = 0; i < MAXmat; ++i) {
            for (re int j = 0; j < MAXmat; ++j) {
                base.mat[i][j] = mat[i][j];
            }
        }
        while (x) {
            if (x & 1) {
                ans = ans * base;
            }
            base = base * base;
            x >>= 1;
        }
        return ans;
    }
};