POJ3233不错的矩阵(矩阵套矩阵)

题意：

给一个n*n的矩阵A，然后求S=A + A^2 + A^3 + ..+ A^k.

思路：

矩阵快速幂，这个题目挺新颖的，以往的矩阵快速幂都是退出公式，然后构造矩阵，这个比较特别，直接上子矩阵吧

A 1 平方后得到 A^2 1+A 三次方 A^3 1+A+A^2

0 1 0 1 0 1 ...这样就行了，

还有注意这个是矩阵套矩阵，然后就是快速幂了，比较容易实现，有一点要注意，

大矩阵的单位矩阵只有对角线才是单位小矩阵，还有一个地方，就是最后我们要在大矩阵的1 2 位置减去单位矩阵，这个减去单位矩阵后如果比0小怎么办，我的处理方法是比0小就再加上余数。

#include<stdio.h>

#include<string.h>

typedef struct

{

    int mat[32][32];

}M;

typedef struct

{

    M MAT[3][3];

}MM;

int n ,MOD;

M matM(M a ,M b)

{

    M c;

    memset(c.mat ,0 ,sizeof(c.mat));

    for(int k = 1 ;k <= n ;k ++)

    for(int i = 1 ;i <= n ;i ++)

    if(a.mat[i][k])

    for(int j = 1 ;j <= n ;j ++)

    c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;

    return c;

}

M addM(M a ,M b)

{

    M c;

    memset(c.mat ,0 ,sizeof(c.mat));

    for(int i = 1 ;i <= n ;i ++)

    for(int j = 1 ;j <= n ;j ++)

    c.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % MOD;

    return c;

}

MM matMM(MM a ,MM b)

{

    MM c;

    for(int i = 1 ;i <= 2 ;i ++)

    for(int j = 1 ;j <= 2 ;j ++)

    for(int k = 1 ;k <= n ;k ++)

    for(int l = 1 ;l <= n ;l ++)

    c.MAT[i][j].mat[k][l] = 0;

    for(int i = 1 ;i <= 2 ;i ++)

    for(int j = 1 ;j <= 2 ;j ++)

    for(int k = 1 ;k <= 2 ;k ++)

    c.MAT[i][j] = addM(c.MAT[i][j] ,matM(a.MAT[i][k] ,b.MAT[k][j]));

    return c;

}

MM quickMM(MM a ,int b)

{

    MM c;

    for(int i = 1 ;i <= 2 ;i ++)

    for(int j = 1 ;j <= 2 ;j ++)

    for(int k = 1 ;k <= n ;k ++)

    for(int l = 1 ;l <= n ;l ++)

    c.MAT[i][j].mat[k][l] = 0;

    for(int k = 1 ;k <= n ;k ++)

    c.MAT[1][1].mat[k][k] = c.MAT[2][2].mat[k][k] = 1;

    while(b)

    {

        if(b & 1) c = matMM(c ,a);

        a = matMM(a ,a);

        b >>= 1;

    }

    return c;

}

int main ()

{

    int i ,j ,b;

    MM A;

    while(~scanf("%d %d %d" ,&n ,&b ,&MOD))

    {

        //MOD = 10000000;

        for(i = 1 ;i <= n ;i ++)

        for(j = 1 ;j <= n ;j ++)

        {

            scanf("%d" ,&A.MAT[1][1].mat[i][j]);

            A.MAT[2][1].mat[i][j] = 0;

            if(i == j)

            A.MAT[1][2].mat[i][j] = A.MAT[2][2].mat[i][j] = 1;

            else  A.MAT[1][2].mat[i][j] = A.MAT[2][2].mat[i][j] = 0;

        }

        MM ans = quickMM(A ,b + 1);

        for(int i = 1 ;i <= n ;i ++)

        for(int j = 1 ;j <= n ;j ++)

        {

            if(i == j) ans.MAT[1][2].mat[i][j] --;

            if(ans.MAT[1][2].mat[i][j] < 0) ans.MAT[1][2].mat[i][j] += MOD;

            if(j == n) printf("%d\n",ans.MAT[1][2].mat[i][j]);

            else printf("%d " ,ans.MAT[1][2].mat[i][j]);

        }

    }

    return 0;

}

巴特西

POJ3233不错的矩阵(矩阵套矩阵)

最新文章

热门文章