【矩阵快速幂】Experienced Endeavour

阳光穿透心脏的1/2处 2022-06-07 05:43 24阅读 0赞

Think:  
1知识点：矩阵快速幂  
2题意：初始时输入一个序列a(0), a(1), … a(n-1)，之后不断构造一个新序列，新序列构造规则为每次选取上次序列的固定位置元素累加  
3题意分析：  
（1）：构造系数矩阵，矩阵快速幂.因为每次对于新序列结点ci，其值与上次序列的固定位置有关系，因此可思考是否可以构造一个0,1系数矩阵，之后每次重复构造新序列时，每构造一次，就乘以0,1系数矩阵一次.  
（2）：对于序列\[a(0), .., a(n-1)\] \* M = \[c(0), …, c(n-1)\]故可知0,1系数矩阵M应为n\*n，进而寻找关系，得到M\[j\]\[i\]:序列ci选择的固定位置j  
4反思：  
（1）：矩阵快速幂的矩阵相乘函数，矩阵乘法公式写错，需要反思，要细心严谨  
（2）：求解pri数组时，矩阵乘法公式写错且忘记取模，需要反思，要专注细心

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int mod = 1000;
    
    struct Matrix{
        int v[54][54];
    };
    
    Matrix multiply(Matrix a, Matrix b, int Matrix_len);
    Matrix matrix_pow(Matrix x, int k, int Matrix_len);
    
    int rec[104], pri[104];
    
    int main(){
        int T, n, r, m, id, i, j, k;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &r);
            for(i = 0; i < n; i++)
                scanf("%d", &rec[i]);
            Matrix x;
            memset(x.v, 0, sizeof(x.v));
            for(i = 0; i < n; i++){
                scanf("%d", &m);
                while(m--){
                    scanf("%d", &id);
                    x.v[id][i] = 1;
                }
            }
            Matrix y = matrix_pow(x, r, n);
            memset(pri, 0, sizeof(pri));
            for(j = 0; j < n; j++){
                for(k = 0; k < n; k++){
                    pri[j] += (rec[k]*y.v[k][j]);
                    pri[j] %= mod;
                }
            }
            for(i = 0; i < n; i++)
                printf("%d%c", pri[i], i == n-1? '\n': ' ');
        }
        return 0;
    }
    Matrix multiply(Matrix a, Matrix b, int Matrix_len){
        Matrix c;
        memset(c.v, 0, sizeof(c.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++){
                    c.v[i][j] += (a.v[i][k]*b.v[k][j]);
                    c.v[i][j] %= mod;
                }
            }
        }
        return c;
    }
    Matrix matrix_pow(Matrix x, int k, int Matrix_len){
        Matrix ans;
        memset(ans.v, 0, sizeof(ans.v));
        for(int i = 0; i < Matrix_len; i++)
            ans.v[i][i] = 1;
        while(k){
            if(k & 1)
                ans = multiply(ans, x, Matrix_len);
            x = multiply(x, x, Matrix_len);
            k >>= 1;
        }
        return ans;
    }

[vjudge]: https://vjudge.net/problem/UVA-11551