题目大意

给你一个n*n(n <= 30)的矩阵A， 每个元素x（0 <=x<= 1e6 ）， 给你一个m（m <= 1e9）， 求S = A + A^2 + A ^3 + … + A^m,其中对每个元素对1e9+7取余。

分析

这里有另一种做法， 点此

对于A矩阵， 我们可以构造一个这样的矩阵B

1
2
|A A|
|0 E|

B^2为

1
2
|A^2 A + A^2|
|0   E      |

B^3为

1
2
|A^3 A + A^2 + A^3|
|0   E            |

因此只要求B^m 即可。

代码

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
#include <bits/stdc++.h>
using namespace std;

#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}

struct matrix {
    int dimx, dimy; // 矩阵维度
    ll m[100][100];
    matrix(int x = 60, int y = 60) { // 构造函数
        ms(m, 0);
        dimx = x, dimy = y;
    }
    matrix operator*(const matrix &x) const {
        matrix c;
        for (int i = 0; i < dimx; ++i)
            for (int j = 0; j < x.dimy; ++j)
                for (int k = 0; k < dimy; ++k)
                    c.m[i][j] = (c.m[i][j] + m[i][k] * x.m[k][j]) % mod;
        return c;
    }
};

matrix qpow2(matrix a, int b) {
    matrix ans = a;b--;
    while (b) {
        if (b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
int main(){
    int n = read(), m = read();
    matrix a(2 * n, 2 * n);
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            a.m[i][j + n] = a.m[i][j] = read();
        }
    }
    for (int i = n; i < 2 * n; ++i) a.m[i][i] = 1;
    a = qpow2(a, m);
    for (int i = 0; i < n; ++i){
        for (int j = n; j < 2 * n; ++j){
            printf("%d", a.m[i][j]);
            if (j != 2 * n - 1) putchar(' ');
            else putchar(10);
        }
    }
    
    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。