关于kuangbin矩阵专题内题目的小结

关于kuangbin矩阵专题内题目的小结

大致从这几点分类来小结:

  1. 矩阵运算的简单优化
  2. 取模要求的些许处理
  3. 结合矩阵的优化操作
  4. 各式各样的构造思路
  5. 常常要求的求和操作

1.矩阵运算的简单优化

根据结合律,调整矩阵的运算顺序有时可能会有显著优化,这取决于矩阵的形状,如:【HDU-4965】Fast Matrix Calculation

对于稀疏矩阵,我们可以稍微调整一下矩阵乘法内部的循环顺序,就可以实现先判断其中一个矩阵要相乘的那个位置上是否是0,如果是则不用去遍历另一个矩阵与它相乘的元素,因为结果一定都是0,如:【UVA-11651】Krypton Number System

另外,我们可以直接将记录着初始数据的那个列向量(因为我比较习惯的形式是\(A_n = TA_{n – 1}\)),我们在解决竞赛程序问题时,可以对矩阵快速幂这个函数要返回的那个矩阵结果初始化为这个列向量,只要把它排到第一列上,后面几列保持0,而不用初始化为单位矩阵,这样做之后,矩阵内可能出现大量的0,结合上面的稀疏矩阵的简单优化,可以获得一个不错的效果。同时,这样做也能够有效减少代码量,如:【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】【FZU-1911】Construct a Matrix【构造问题】。【对于一个斐波那契数列,我们可以直接从第二列来获得某一项的结果】。

对于循环矩阵,我们注意到循环矩阵与循环矩阵相乘结果一定是循环矩阵,所以只需要维护一行就可以,而不需要一直维护多行,这样可以有效减少复杂度\(n^3 \rightarrow n^2\),如:【UVA-1386】Cellular Automaton【循环矩阵的矩阵快速幂】

2.取模要求的些许处理

取模也是常常碰到的问题,有的需要将负数取模变成正数:【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】,有的可能需要计算出取模值:【UVA – 10689】Yet another Number Sequence等。

3.结合矩阵的优化操作

dp问题,有时我们可以发现转移规律具有不变性,同时我们判断出这个单次转移的最远距离可以开矩阵来解决,这样我们就可以使用矩阵快速幂来进行状态转移:【UVA-11651】Krypton Number System

4.各式各样的构造思路

简单移项:【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】

适当修改一些初始值来补全递推关系:【HDU-5015】233 Matrix【矩阵快速幂】

分类讨论得到统一的递推关系:【HDU-4990】Reading comprehension

推导公式中局部的递推关系,比如幂次符合递推:【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

根据每一个状态构建多元组,找到状态转移的不变规律:【CodeForces-385E】Bear in the Field【矩阵快速幂】

使用组合数来构建:【CodeForces-392C】Yet Another Number Sequence

将表达式剥离出一定的项,得到的表达式系数满足递推关系:【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

更多情况下,对于题目给出递推式,一种思路是列出前几项找递推关系:【UVA-10655】Contemplation! Algebra【矩阵快速幂】,另一种思路是,直接将一个式子中包含当前项的数全都转化上一项:【HDU-4686】Arc of Dream【矩阵快速幂】

5.常常要求的求和操作

求和常见两种操作,一种是给转移矩阵加一行记录求和值:【HDU-4686】Arc of Dream【矩阵快速幂】【FZU-1911】Construct a Matrix【构造问题】,还有一种是找到可行的分治策略:【UVA-11149】Power of Matrix【矩阵快速幂】

 

其它:降幂操作:使用费马小定理【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

【HDU-4686】Arc of Dream【矩阵快速幂】

【HDU-4686】Arc of Dream【矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-4686

Solution:

对于要求求和的问题,常见两种递推情况,一种是求和后的每项满足递推关系,另一种是每一项满足递推关系,需要给最后的变换矩阵另外加一行记录求和。这道题属于第二种,能够很简单就推出单项递推关系:

\(a_nb_n = AX \times BXa_{n – 1}b_{n – 1} + AX \times BYa_{n – 1} + BX \times AYb_{n – 1} + AY \times BY\)

根据这个来建立矩阵,接着用矩阵快速幂来计算。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const int LIM = 5;
LL n, a0, ax, ay, b0, bx, by;
struct Matrix {
    LL v[LIM][LIM];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++)
            for (int k = 0; k < LIM; k++)
                if (v[i][k])
                    for (int j = 0; j < LIM; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
        return ret;
    }
};

LL fastPow(LL p, Matrix base) {
    Matrix ret = {0};
    ret.v[0][0] = a0 * b0 % MOD;
    ret.v[1][0] = a0;
    ret.v[2][0] = b0;
    ret.v[3][0] = 1;
    ret.v[4][0] = a0 * b0 % MOD;
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret.v[4][0];
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> n >> a0 >> ax >> ay
        >> b0 >> bx >> by) {
        if (!n) {
            cout << 0 << "\n";
            continue;
        }
        ax %= MOD, bx %= MOD, ay %= MOD, by %=MOD, a0 %= MOD, b0 %= MOD;
        Matrix base = {ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 0,
            0, ax, 0, ay, 0,
            0, 0, bx, by, 0,
            0, 0, 0, 1, 0,
            ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 1};
        cout << fastPow(n - 1, base) << "\n";
    }
    return 0;
}

 

【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-4549

Solution:

首先应该注意到,如果将每一项都使用a、b的幂的积来表示,它们各自的幂次都是斐波那契数列中的项,并且二者只差一项。接着注意到,幂次是斐波那契数列,当然也需要取模,但是不能随便取,当然也不能取1000000007【注意:\(a^b % c \neq (a %c)^{b%c}%c\),一定要注意这一点】,所以使用费马小定理得知幂次应当对1000000006取模。

参考了:https://blog.csdn.net/u013050857/article/details/44999127,感谢博主的分享。

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const LL EXMOD = 1e9 + 6;
const int LIM = 2;
LL a, b, n;

struct Matrix {
    LL v[LIM][LIM];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++)
            for (int k = 0; k < LIM; k++)
                if (v[i][k])
                    for (int j = 0; j < LIM; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j] % EXMOD) % EXMOD;
        return ret;
    }
};

Matrix fastPow(LL p, Matrix base) {
    Matrix ret = {1, 0, 0, 0};
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret;
}

LL fastPow(LL p, LL base) {
    LL ret = 1;
    while (p) {
        if (p & 1) ret = ret * base % MOD;
        p >>= 1;
        if (p) base = base * base % MOD;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    const Matrix base = {1, 1, 1, 0};
    while (cin >> a >> b >> n) {
        if (n == 0) cout << a << "\n";
        else if (n == 1) cout << b << "\n";
        else {
            Matrix trans = fastPow(n - 1, base);
            cout << fastPow(trans.v[1][0], a) * fastPow(trans.v[0][0], b) % MOD << "\n";
        }
    }
    return 0;
}

 

【UVA-10518】How Many Calls?【矩阵快速幂】

【UVA-10518】How Many Calls?【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-10518

Solution:

题目说,这道题我们不关心Fibonacci数列,实际上。。它还是个类似的斐波那契数列,只不过有变化,我们使用\(F_n\)来表示新数列的第n项,经过分析,有:

\(F_0 = 1\),

\(F_1 = 1\),

\(F_n = F_{n – 1} + F_{n – 2} + 1\).

根据这个来写矩阵快速幂就好,复杂度\(O(3^3logn)\)。

另外,关于输入结束,虽然题目说n和m都是0的时候结束,但是我们根据这两个值发现,在合法情况下,n可能是0,而m不能为0,那么判断结束只要判断m是不是0就可以,不用管n。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;
ULL n, m;

const int LIM = 3;
struct Matrix {
    ULL v[LIM][LIM];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < LIM; i++)
            for (int k = 0; k < LIM; k++)
                if (v[i][k])
                    for (int j = 0; j < LIM; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % ::m;
        return ret;
    }
};

ULL fastPow(ULL p, Matrix base) {
    Matrix ret = {0};
    for (int i = 0; i < LIM; i++) ret.v[i][0] = 1;
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret.v[1][0];
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    Matrix base = {1, 1, 1, 1, 0, 0, 0, 0, 1};
    for (int k = 1; cin >> n >> m && m; k++) {
        cout << "Case " << k << ": " << n << " " << m << " ";
        if (n) cout << fastPow(n, base) % m << "\n";
        else cout << 1 % m << "\n";
    }
    return 0;
}

 

【FZU-1911】Construct a Matrix【构造问题】

【FZU-1911】Construct a Matrix【构造问题】

问题链接:https://vjudge.net/problem/FZU-1911

Solution:

矩阵的大小使用矩阵快速幂来求就好,方法是,给以往的斐波那契变换矩阵加上一行,用来记录和值。接着就是一个构造问题了,我们写一个程序来单独跑dfs【为了编码方便,我就使用python3来写了,毕竟代码会精简一些】,需要的功能是,给出一个边长,遍历所有可能的矩阵,都进行输出:

import numpy as np
# try to build a valid matrix by using dfs
def dfs(size, crt, ans):
    if crt == size * size:
        vis = set([])
        csum = np.zeros(size, int)
        for i in range(size):
            rsum = 0
            for j in range(size):
                rsum = rsum + ans[i * size + j]
                csum[j] = csum[j] + ans[i * size + j]
            if rsum in vis:
                return False
            vis.add(int(rsum))
        for j in range(size):
            if csum[j] in vis:
                return False
            vis.add(int(csum[j]))
        print("Find one solution!")
        print(ans.reshape(size, size))
        return True
    flag = False
    for i in range(-1, 2):
        ans[crt] = i
        # print("Current : ", ans)
        flag = dfs(size, crt + 1, ans) or flag
    return flag

size = int(input("The size of matrix to construct:"))
ans = np.zeros(size * size, int);
if not dfs(size, 0, ans):
    print("Unfortunately, there are no valid solutions!")
else:
    print("All solution have been showed!")

首先我们可以发现的是,如果边长是奇数或者0,是不存在符合要求的矩阵的,接着就是找偶数的情况。按照上面的程序,输出会很多,我们通过一些猜想来做些简单的修改,来添加一些要求,让它不要把任何满足要求的排列的矩阵都输出。最后我们可以发现一种构造方法:对于n阶矩阵,如果n是一个非零偶数,那么总存在至少一种排列方法,使得其满足:只包含0,-1,1三种元素,且各行各列的和值不相同,其中一种有效的构造方法是,将矩阵按照一条对角线分隔开,对角线上方放置1或-1,下方放置与上方的数相反的数,分割用的对角线上交替放置0,1或0,-1。

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long LL;
const int LIM = 200 + 10;
int size;
LL n, m;
int ans[LIM * LIM];
int csum[LIM], rsum;

struct Matrix {
    LL v[3][3];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < 3; i++)
            for (int k = 0; k < 3; k++)
                if (v[i][k])
                    for (int j = 0; j < 3; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % ::m;
        return ret;
    }
};

int fibonacci(LL n, Matrix base) {
    Matrix ret = {0};
    ret.v[0][0] = ret.v[1][0] = 1;
    while (n) {
        if (n & 1) ret = base * ret;
        n >>= 1;
        if (n) base = base * base;
    }
    return ret.v[2][0];
}

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int t;
    cin >> t;
    Matrix base = {1, 1, 0, 1, 0, 0, 0, 1, 1};
    for (int k = 1; k <= t; k++) {
        cin >> n >> m;
        size = fibonacci(n, base);
        if (!size || size & 1) {
            cout << "Case " << k << ": No" << "\n";
        } else {
            cout << "Case " << k << ": Yes" << "\n";
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (j) cout << ' ';
                    if (i == j) cout << (i & 1 ? 0 : -1);
                    else if (j < i) cout << 1;
                    else cout << -1;
                }
                cout << '\n';
            }
        }
    }
    return 0;
}

 

【CodeForces-385E】Bear in the Field【矩阵快速幂】

【CodeForces-385E】Bear in the Field【矩阵快速幂】

问题链接:https://vjudge.net/problem/CodeForces-385E

Solution:

注意到t很大,直接模拟会超时。

注意到x和y相关【二者共同决定速度的增量】,时间影响对速度也有影响【每一秒都会为每个单元贡献一个生长,从而影响熊的速度增量】,同时注意到,熊不会吃光每个树丛上的草莓【所以速度增量与是否走过当前方格无关】。

接着,发现总可以由上一个状态的x, y, dx, dy, t推出当前状态的对应值,并且推导方式固定,所以可以使用矩阵快速幂将复杂度降到\(O(6^3logt)\)。

注意到坐标范围1到n,取模的形式很麻烦,我们对原始坐标减1进行一次映射,新的坐标按照原来的顺序落在了0到n-1。

#include <iostream>

using namespace std;

typedef long long LL;

const int SIZE = 6;
LL n, sx, sy, dx, dy, t;
struct Matrix {
    LL v[SIZE][SIZE];
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {0};
        for (int i = 0; i < SIZE; i++) {
            for (int k = 0; k < SIZE; k++) {
                if (v[i][k]) {
                    for (int j = 0; j < SIZE; j++) {
                        ret.v[i][j] = ((ret.v[i][j] + v[i][k] * m.v[k][j] % n) + n) % n;
                    }
                }
            }
        }
        return ret;
    }
};

Matrix powMod(LL p, Matrix base) {
    Matrix ret = {0};
    ret.v[0][0] = sx - 1, ret.v[1][0] = sy - 1;
    ret.v[2][0] = dx, ret.v[3][0] = dy;
    ret.v[4][0] = 1, ret.v[5][0] = 0;
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    cin >> n >> sx >> sy >> dx >> dy >> t;
    Matrix base = {0};
    base.v[0][0] = base.v[0][4] = 2;
    base.v[0][1] = base.v[0][2] = base.v[0][5] = 1;
    base.v[1][1] = base.v[1][4] = 2;
    base.v[1][0] = base.v[1][3] = base.v[1][5] = 1;
    base.v[2][0] = base.v[2][1] = base.v[2][2] = base.v[2][5] = 1;
    base.v[3][0] = base.v[3][1] = base.v[3][3] = base.v[3][5] = 1;
    base.v[2][4] = base.v[3][4] = 2;
    base.v[4][4] = 1;
    base.v[5][4] = base.v[5][5] = 1;
    base = powMod(t, base);
    cout << base.v[0][0] + 1 << " " << base.v[1][0] + 1 << "\n";
    return 0;
}

 

【CodeForces-392C】Yet Another Number Sequence

【CodeForces-392C】Yet Another Number Sequence

问题链接:https://vjudge.net/problem/CodeForces-392C

Solution:

我们将每一个\(A_i\)展开,发现它是许多项的和,准确来说,是以前出现过的项乘上一个组合数,根据这个建立转移矩阵。

参考了:https://www.cnblogs.com/MyWither/p/3556523.html,感谢博主分享。

#include <iostream>
using namespace std;

typedef long long LL;
const int LIM = 90;
const int SIZE = 50;
const LL MOD = 1e9 + 7;
LL n, C[SIZE][SIZE];
int k;

struct Matrix {
    LL v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++)
            for (int k = 0; k < size; k++)
                if (v[i][k])
                    for (int j = 0; j < size; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j] % MOD) % MOD;
        return ret;
    }
};

Matrix fastPow(LL p, Matrix base) {
    Matrix ret = {{0}};
    ret.size = base.size;
    for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret;
}

void buildC() {
    for (int i = 0; i <= k; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
}

int main(void) {
    scanf("%lld%d", &n, &k);
    buildC();
    Matrix base = {{0}};
    base.size = (k + 1) * 2 + 1;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= i; j++)
            base.v[i][j] = base.v[i][j + k + 1] = base.v[i + k + 1][j] = C[i][j];
    base.v[base.size - 1][base.size - 1] = base.v[base.size - 1][k] = 1;
    base = fastPow(n, base);
    LL ans = 0;
    for (int i = 0; i < base.size - 1; i++)
        ans = (ans + base.v[base.size - 1][i]) % MOD;
    printf("%lld\n", ans);
    return 0;
}

 

【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

问题链接:https://vjudge.net/problem/HDU-4565

Solution:

关键在于找到不变形式\(A+B\sqrt{b}\),写出前几个n对应的A和B,列个表格就可以很快找到转移规律。

解决向上取整问题办法是本题的亮点,下面链接中的博文。

参考了:https://blog.csdn.net/Ramay7/article/details/50947293

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
LL MOD, a, b;
struct Matrix {
    LL v[2][2];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
        return ret;
    }
};

Matrix fastPow(int p, Matrix base) {
    Matrix ret = {a, 0, 1, 0};
    while (p) {
        if (p & 1) ret = base * ret;
        base = base * base;
        p >>= 1;
    }
    return ret;
}

int main(void) {
    int n;
    while (~scanf("%lld%lld%d%lld", &a, &b, &n, &MOD)) {
        Matrix base = {a, b, 1, a};
        base = fastPow(n - 1, base);
        printf("%lld\n", base.v[0][0] * 2 % MOD);
    }
    return 0;
}

 

【UVA-10870】Recurrences【矩阵快速幂】

【UVA-10870】Recurrences【矩阵快速幂】

问题链接:https://vjudge.net/problem/UVA-10870

Solution:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int MOD = 0;
const int LIM = 20;
struct Matrix {
    LL v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k])
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
            }
        }
        return ret;
    }
};

Matrix fastPow(int p, Matrix m) {
    Matrix ret = {0};
    ret.size = m.size;
    for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        m = m * m;
        p >>= 1;
    }
    return ret;
}

LL input[LIM], output[LIM];
Matrix base;

int main() {
    int d, n;
    while (~scanf("%d%d%d", &d, &n, &MOD) && (d || n) && MOD) {
        memset(&base, 0, sizeof base);
        base.size = d;
        for (int i = 0; i < d; i++)
            scanf("%lld", &base.v[0][i]), base.v[0][i] %= MOD;
        for (int i = 1; i < d; i++)
            base.v[i][i - 1] = 1;
        for (int i = 0; i < d; i++)
            scanf("%lld", &input[d - 1 - i]), input[d - 1 - i] %= MOD;
        if (n <= d) printf("%lld\n", input[d - n]);
        else {
            base = fastPow(n - d, base);
            LL ans = 0;
            for (int i = 0; i < d; i++) {
                ans = (ans + base.v[0][i] * input[i]) % MOD;
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

 

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

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

问题链接:https://vjudge.net/problem/UVA-1386

Solution:

这道题的材料很有意思,是关于元胞自动机的【说到元胞自动机自然能够想到那个很有意思的康威的生命游戏 (Conwey’s Game of LIfe)了】,不过。。和这道题关系不大。

元胞自动机,给定一个演化规则,每个单位时间将根据演化规则更新所有的单元,这道题的演化规则就是将每个单元更新为在d-enviroment【也就是在这个环上对于每个单元的距离小于等于d的“邻居”了】之内的数量和,使用矩阵快速幂来解决。

但是。。。n最大是500,事情显然没有顺利到直接就可以解决,遇到两个问题:\(n^3\)复杂度会超时,以及500*500的long long矩阵能不能开成都是个问题。

这时我们注意到这道题的变换矩阵是一个循环矩阵,循环矩阵与循环矩阵相乘仍然是一个循环矩阵,利用这个性质,我们可以只维护一行的数据,同时将空间由\(O(n^2)\)降到\(O(n)\)以及时间由\(O(n^3)\)降到\(O(n^2)\),具体做法我们可以通过写出矩阵,来观察一下这个循环矩阵列上的元素能够对应到哪一行。

如果还不放心可以写个小demo试验一下:

#include <iostream>


using namespace std;

struct Matrix {
    int v[10];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                ret.v[i] += v[j] * m.v[(size - i + j) % size];
            }
        }
        return ret;
    }
};

Matrix fastPow(int k, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    ret.v[0] = 1;
    while (k) {
        if (k & 1) ret = ret * m;
        if (k) m = m * m;
        k >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, k;
    while (cin >> n && n) {
        Matrix input;
        input.size = n;
        for (int i = 0; i < n; i++)
            cin >> input.v[i];
        while (cin >> k && k) {
            Matrix output = fastPow(k, input);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j) cout << ' ';
                    cout << output.v[(n - i + j) % n];
                }
                cout << endl;
            }
        }
    }
    return 0;
}

下面是AC的代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int n, mod, d, k;
const int LIM = 500 + 10;
struct Matrix {
    LL v[LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                ret.v[i] = (ret.v[i] + v[k] * m.v[(size - i + k) % size]) % mod;
            }
        }
        return ret;
    }
};
Matrix build() {
    Matrix ret = {{0}};
    ret.size = n;
    for (int i = 0; i <= d; i++)
        ret.v[i] = ret.v[(n - i) % n] = 1;
    return ret;
}
Matrix fastPow(int p, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    ret.v[0] = 1;
    while (p) {
        if (p & 1) ret = ret * m;
        p >>= 1;
        if (p) m = m * m;
    }
    return ret;
}
LL input[LIM], output[LIM];

int main() {
    while (~scanf("%d%d%d%d", &n, &mod, &d, &k)) {
        memset(output, 0, sizeof output);
        for (int i = 0; i < n; i++)
            scanf("%d", &input[i]);
        Matrix trans = build();
        trans = fastPow(k, trans);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                output[i] = (output[i] + trans.v[(n - i + k) % n] * input[k]) % mod;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i) putchar(' ');
            printf("%d", output[i]);
        }
        putchar('\n');
    }
    return 0;
}

注意:如果这题数组开int会WA。