【循环矩阵+矩阵快速幂】Cellular Automaton UVA - 1386

╰+哭是因爲堅強的太久メ 2022-06-06 20:45 163阅读 0赞

Think:  
1知识点：循环矩阵+矩阵快速幂  
2题意：输入n(1<=n<=500), m(1<=n<=1000000), d(0<=d<(n/2)), k(1<=k<=10000000)然后输入一个n个数的环，数的范围为\[0,m-1\]，然后进行k次变换，变换为：取环中当前元素，然后取其左边d个数，取其右边d个数，然后相加取模m，询问经过k次变换之后的序列  
3题意思考：  
（１）：写出系数矩阵，会发现系数矩阵n\*n太大，空间复杂度和时间复杂度都相对过大，进而通过循环矩阵性质，将空间复杂度由二维矩阵优化至一维矩阵，矩阵乘法的时间复杂度由n^3优化至n^2  
4反思：  
（１）：函数形参传入为常变量时，无法在函数内改变传入的常变量的值  
（２）：矩阵运算的性质以及特殊矩阵的性质需要复习回顾

以下为Accepted代码

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