蓝桥杯算法训练 ALGO-60 矩阵乘法

迷南。 2023-10-06 09:42 62阅读 0赞

算法训练 矩阵乘方

时间限制：1.0s 内存限制：512.0MB

问题描述

给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。  
　　其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。  
　　要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：  
　　若b=0，则A^b%m=I%m。其中I表示单位矩阵。  
　　若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。  
　　若b为奇数，则A^b%m=(A^(b-1)%m)\*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。  
　　这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2x2的矩阵，m不大于10000。

输入格式

输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。

输出格式

输出两行，每行两个整数，表示A^b%m的值。

样例输入

2 2  
1 1  
0 1

样例输出

1 0  
0 1

**题目解析：**

**　　题目中已经给出了解题思路，只需分情况讨论 b 为不同情况时，矩阵该怎样去乘即可。**

**　　因为C/C++中无法返回二维数组，所以给出两种代码，一种是常规方式，一种为结构体，但思路如题所示。后者较前者的时间复杂度更高，但空间复杂度大致相同。**

示例代码1：

1 #include<iostream>
      2 #include<memory.h>
      3 using namespace std;
      4 
      5 #define MAX_NUM 2
      6 
      7 //数组copy 将源数组s复制给目的数组o 
      8 void arrcopy(int s[][MAX_NUM], int o[][MAX_NUM])
      9 {
     10     for (int i = 0; i < MAX_NUM; i++)
     11     {
     12         for (int j = 0; j < MAX_NUM; j++)
     13         {
     14             o[i][j] = s[i][j];        
     15         }        
     16     }
     17 }
     18 
     19 /*
     20     矩阵乘法
     21     m：模 
     22 */ 
     23 void matrixMul(int x[][MAX_NUM], int y[][MAX_NUM], int m)
     24 {
     25     int t[MAX_NUM][MAX_NUM];
     26     memset(t, 0, sizeof(t));
     27 
     28     for (int i = 0; i < MAX_NUM; i++)
     29     {
     30         for (int j = 0; j < MAX_NUM; j++)
     31         {
     32             for (int k = 0; k < MAX_NUM; k++)
     33             {
     34                 t[i][j] += x[i][k] * y[k][j];
     35                 t[i][j] %= m;
     36             }
     37         }
     38     }
     39     
     40     arrcopy(t , x); //最终结果保存在数组x 
     41 }
     42 
     43 //分情况处理 
     44 void dispose(int A[][MAX_NUM], int b, int m)
     45 {
     46     if (b == 0)
     47     {
     48         int tmp;
     49         for (int i = 0; i < MAX_NUM; i++)
     50         {
     51             for (int j = 0; j < MAX_NUM; j++)
     52             {
     53                 if (i == j)
     54                     tmp = 1;
     55                 else
     56                     tmp = 0;
     57                 A[i][j] = tmp % m;    //A为单位矩阵 A^b%m=I%m
     58             }
     59         }
     60         return;
     61     }
     62     
     63     if (b % 2 == 0)    //A^b%m=(A^(b/2)%m)^2%m
     64     {
     65         dispose(A, b / 2, m);
     66         matrixMul(A, A, m);
     67     }
     68     else            //A^b%m=(A^(b-1)%m)*a%m
     69     {
     70         int t[MAX_NUM][MAX_NUM];
     71         arrcopy(A , t);
     72         dispose(A, b - 1, m);
     73         matrixMul(A, t, m);
     74     }
     75 }
     76 
     77 int main()
     78 {
     79     int b, m;
     80     scanf("%d%d", &b, &m);
     81     
     82     int A[MAX_NUM][MAX_NUM];
     83     for (int i = 0; i < MAX_NUM; i++)
     84     {
     85         for (int j = 0; j < MAX_NUM; j++)
     86         {
     87             scanf("%d", &A[i][j]);        
     88         }        
     89     }
     90     
     91     dispose(A, b, m);
     92     
     93     for (int i = 0; i < MAX_NUM; i++)
     94     {
     95         for (int j = 0; j < MAX_NUM; j++)
     96         {
     97             printf("%d ", A[i][j] % m);        
     98         }
     99         printf("\n");        
    100     }
    101 
    102     return 0;
    103 }

示例代码2：

1 #include<iostream>
     2 using namespace std;
     3 
     4 #define MAX_NUM 2
     5 
     6 struct Matrix
     7 {
     8     int arr[MAX_NUM][MAX_NUM];    
     9 };
    10 
    11 Matrix A;
    12 
    13 //矩阵乘法，与m取模，返回结果 
    14 Matrix mul(Matrix x, Matrix y, int m)
    15 {
    16     Matrix t;    
    17     for (int i = 0; i < MAX_NUM; i++)
    18     {
    19         for (int j = 0; j < MAX_NUM; j++)
    20         {
    21             t.arr[i][j] = 0;
    22             for (int k = 0; k < MAX_NUM; k++)
    23             {
    24                 t.arr[i][j] += x.arr[i][k] * y.arr[k][j];
    25                 t.arr[i][j] %= m;
    26             }
    27         }
    28     }
    29     return t;
    30 }
    31 
    32 //分情况处理 
    33 Matrix dispose(Matrix A, int  b, int m)
    34 {
    35     if (b == 0)
    36     {
    37         for (int i = 0; i < MAX_NUM; i++)
    38         {
    39             for (int j = 0; j < MAX_NUM; j++)
    40             {
    41                 if (i == j)
    42                     A.arr[i][j] = 1 % m;
    43                 else
    44                     A.arr[i][j] = 0 % m;        
    45             }        
    46         }
    47         return A;
    48     }
    49     
    50     Matrix t = dispose(A, b / 2, m);
    51     if (b % 2 == 0)
    52         return mul(t, t, m);
    53     else    //当b为奇数时，先计算A^(b/2)次方，再乘以A，即A^(b-1)*A 
    54              //例如，b=5，b/2=2，即A^5 = (A^2 * A^2) * A 
    55         return mul(mul(t, t, m), A, m);
    56 }
    57 
    58 int main()
    59 {
    60     int b, m;
    61     scanf("%d%d", &b, &m);
    62 
    63     for (int i = 0; i < MAX_NUM; i++)
    64     {
    65         for (int j = 0; j < MAX_NUM; j++)
    66         {
    67             scanf("%d", &A.arr[i][j]);        
    68         }        
    69     }
    70     
    71     Matrix p = dispose(A, b, m);
    72     
    73     for (int i = 0; i < MAX_NUM; i++)
    74     {
    75         for (int j = 0; j < MAX_NUM; j++)
    76         {
    77             printf("%d ", p.arr[i][j]);        
    78         }
    79         printf("\n");
    80     }
    81      
    82     return 0;
    83 }