问题描述:

给你一个$n*n$的矩阵$A$和一个整数$k$,需要你求出矩阵$S=A+A^2+A^3+···+A^K$

输入:

第一行三个整数$n(n<=30), k(k<=10^9), m(m<=10000)$

输出:

输出模$m$意义下的矩阵$S$

思路:

一道矩阵的好题。我们一般都是将矩阵用于加速递推上,这道题却是让你求一个矩阵。

虽然要你求一个矩阵,然而一样可以使用矩阵加速递推的思路。我们可以将式子$A+A^2+A^3+···+A^K$看作是由$A+A^2+A^3+···+A^{k-1}$乘上$A$再加$A$递推而来,递推的初始值就是$A$。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int n, k, m, a[100][100], b[100][100];

void mul(int a[100][100], int b[100][100])
{
    int c[100][100];
    memset(c, 0, sizeof(c));
    for(int i=1; i<=n*2; i++)
        for(int j=1; j<=n*2; j++)
            for(int k=1; k<=n*2; k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;
    memcpy(a, c, sizeof(c));
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
        a[i][i+n]=a[i+n][i+n]=1;
    }
    memcpy(b, a, sizeof(b));
    while(k)
    {
        if(k&1) mul(b, a);
        k>>=1; mul(a, a);
    }
    for(int i=1; i<=n; i++) b[i][i+n]=(b[i][i+n]-1+m)%m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) printf("%d ", b[i][j+n]);
        printf("\n");
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注