【矩阵快速幂】233 Matrix HDU - 5015

我不是女神ヾ 2022-06-07 03:37 165阅读 0赞

Think:  
1知识点：矩阵快速幂  
2题意：定义一个233矩阵，第一行形如233， 23333， 233333， 233…（即a\[0\]\[1\] = 233, a\[0\]\[2\] = 2333,a\[0\]\[3\] = 23333, a\[0\]\[4\] = 233…）,现输入n列的第一个数（即a\[1\]\[0\], a\[2\]\[0\], … , a\[n\]\[0\]），询问a\[n\]\[m\](n ≤ 10,m ≤ 1e9)的值  
3思路：  
（1）：由题意可知m范围可达到1e9，进而思考是否可寻找到第m列和第m-1列的关系  
第一列：  
a1  
a2  
a3  
a4  
则第二列  
23\*10+3 + a1  
23\*10+3 + a2 + a1  
23\*10+3 + a3 + a2 + a1  
23\*10+3 + a4 + a3 + a2 + a1  
分析第一行和第二行可知，递推关系难点1在于如何找到23和3向下传递的传递关系，难点2在于如何找到ai累加关系的实现  
脑洞——转化  
新的第一列：  
23  
a1  
a2  
a3  
a4  
3  
新的第二列：  
23\*10 + 3  
23\*10+3 + a1  
23\*10+3 + a2 + a1  
23\*10+3 + a3 + a2 + a1  
23\*10+3 + a4 + a3 + a2 + a1  
3  
转化关系？  
![SouthEast][]  
[图像来源博客地址——感谢博主][Link 1]

[vjudge题目链接][vjudge]

[建议参考博客——参考题意分析 & 思路][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 10000007;
    
    struct Matrix{
        LL v[14][14];
    };
    
    Matrix multiply(Matrix x, Matrix y, int Matrix_len);
    Matrix matrix_pow(Matrix a, int k, int Matrix_len);
    
    int main(){
        int n, m, i, j;
        Matrix a, b, c;
        while(~scanf("%d %d", &n, &m)){
            memset(a.v, 0, sizeof(a.v));
            memset(b.v, 0, sizeof(b.v));
            a.v[0][0] = 23;
            for(i = 1; i <= n; i++)
                scanf("%lld", &a.v[i][0]);
            a.v[n+1][0] = 3;
            for(i = 0; i <= n+1; i++){
                i != n+1? b.v[i][0] = 10: b.v[i][0] = 0;
                b.v[i][n+1] = 1;
            }
            for(i = 1; i <= n; i++){
                for(j = 1; j <= i; j++){
                    b.v[i][j] = 1;
                }
            }
            c = matrix_pow(b, m, n+2);
            a = multiply(c, a, n+2);
            printf("%lld\n", a.v[n][0]);
        }
        return 0;
    }
    Matrix multiply(Matrix x, Matrix y, int Matrix_len){
        Matrix z;
        memset(z.v, 0, sizeof(z.v));
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                for(int k = 0; k < Matrix_len; k++){
                    z.v[i][j] += x.v[i][k] * y.v[k][j];
                    z.v[i][j] %= mod;
                }
            }
        }
        return z;
    }
    Matrix matrix_pow(Matrix a, int k, int Matrix_len){
        Matrix b;
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                i == j? b.v[i][j] = 1: b.v[i][j] = 0;
            }
        }
        while(k){
            if(k & 1)
                b = multiply(b, a, Matrix_len);
            a = multiply(a, a, Matrix_len);
            k >>= 1;
        }
        return b;
    }

[SouthEast]: /images/20220607/3634de693d234c739ff7e52be4a8a3be.png
[Link 1]: http://blog.csdn.net/u011721440/article/details/39401515
[vjudge]: https://vjudge.net/problem/HDU-5015