[矩阵]快速幂和乘方和

矩阵乘方和

题目描述

给出一个n*n的矩阵A和正整数k,请求出S=A+A^2+A^3+A^4+...+A^k的值.A^x表示x个A相乘的结果.

关于输入

输入包含一组数据.
第一行是三个正整数n k m, (n<=30,k<=1000000000,m<=10000).
接下来n行,每行n个数,表示这个矩阵.

关于输出

输出矩阵S对m取模后的值（即：每个元素对 m 取余）,包括n行,每行n个数

例子输入

2 2 4
0 1
1 1

例子输出

1 2
2 3

解题分析

稍稍观察一下题目所给的数据就可以发现，这个数据量实在是太过于庞大了，单纯地去计算难以满足题目对于时间的要求，必须要有一些好的方法优化算法以解决问题。

首先，这里先引入一个经典的算法——矩阵快速幂。这个算法可以快速地求出高次矩阵。正常来说，我们要求矩阵A^k，我们可能是作k-1次矩阵的乘法，然后得出结果。不过，这样的话也存在一些问题，一旦k过大，我们需要操作的次数是不是就多了？算法的时间复杂度太高了！所以，我们又可以想到一些其他的方法辅助我们。其实可以想到k可以分解为一个二进制编码，比如k=10(10)，转为二进制就是k=1010(2)，所以A^10=A^1010(2)=A*A^(2^1)*A^(2^3)，也就是说，我们可以一位一位地用按位运算 与（&）和1进行运算，若结果为真就乘上一个A矩阵的某个次幂，而这又需要我们用矩阵乘法去更新A矩阵，我们每次都倍增A矩阵的次幂，去维护这个一个变量即可。

有了快速幂之后，距离问题的解决更近了一步，但是还是存在一些问题，现在如果硬要去计算的话结果自然还是超时的，因为k达到了惊人的1000000000。这个时候就有一个关于矩阵的连续次幂和的一个算法了。

那么，我们只需利用快速幂求出后面那个矩阵的k次方，再乘上一个矩阵就可以得到Sk了。

代码实现

#include <iostream>
#include <cstring>
#define MAXN 35
using namespace std;

struct Matrix{
	int m[MAXN*2][MAXN*2];
};
int n,k,m;

Matrix mul(Matrix &a,Matrix &b){
	Matrix temp;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			temp.m[i][j]=0;
			for(int k=1;k<=n;k++){
				temp.m[i][j]+=(a.m[i][k]*b.m[k][j]%m);
				temp.m[i][j]%=m;
			}
		}
	return temp;
}

Matrix quickExp(Matrix &a,int x){
	Matrix mat;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			mat.m[i][j]=(i==j ? 1 : 0);
		}
	for(;x;x>>=1){
		if(x & 1){
			mat=mul(a,mat);
		}
		a=mul(a,a);
	}
	return mat;
}


int main(){
	scanf("%d%d%d",&n,&k,&m);
	Matrix mat1,mat2;
	memset(mat1.m,0,sizeof(mat1.m));
	memset(mat2.m,0,sizeof(mat2.m));
	for(int i=1;i<=n;i++){
		mat2.m[i][i]=mat2.m[i+n][i]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=n+1;j<=2*n;j++){
			scanf("%d",&mat1.m[i][j]);
			mat2.m[n+i][j]=mat1.m[i][j];
		}
	n*=2;
	mat2=quickExp(mat2,k);
	mat1=mul(mat1,mat2);
	for(int i=1;i<=n/2;i++)
		for(int j=1;j<=n/2;j++){
			printf("%d",mat1.m[i][j]);
			if(j!=n/2) printf(" ");
			else printf("\n");
		}
	return 0;
}

这段代码是用来计算矩阵乘方和的问题。下面是代码解决问题的思路和想法的详细描述：

1. 首先，定义了一个结构体 Matrix，用来表示矩阵。矩阵的大小为 MAXN2 * MAXN2。

2. 定义了一个矩阵相乘的函数 mul，用来计算两个矩阵相乘的结果。在计算过程中，需要对每个元素进行模 m 运算。

3. 定义了一个快速幂函数 quickExp，用来计算矩阵的快速幂。该函数接受一个矩阵和一个指数作为参数，返回矩阵的指数次幂结果。

4. 在主函数中，读入输入的 n、k、m。

5. 创建两个矩阵 mat1 和 mat2。其中，mat1 用于存储输入的矩阵，mat2 用于存储快速幂的结果。

6. 初始化 mat2，将其对角线上的元素设置为 1。

7. 读入输入的矩阵，将其存储到 mat1 和 mat2 中。

8. 将 n 值乘以 2，用于表示扩展后的矩阵大小。

9. 调用 quickExp 函数，将 mat2 的 k 次幂存储到 mat2 中。

10. 调用 mul 函数，计算 mat1 和 mat2 相乘的结果，存储到 mat1 中。

11. 输出 mat1 的前 n/2 行和前 n/2 列，即为最终结果。

这段代码使用了快速幂算法来计算矩阵的指数次幂，从而实现了高效的矩阵乘方和的计算。通过对每个元素进行模 m 运算，可以得到最终结果对 m 取模后的值。