欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-03 18:46:40
...

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
转化关系?
【矩阵快速幂】233 Matrix HDU - 5015
图像来源博客地址——感谢博主

vjudge题目链接

建议参考博客——参考题意分析 & 思路

以下为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;
}