杭电1575-Tr A(矩阵快速幂)

2024-05-11 03:48
文章标签 快速 矩阵 杭电 tr 1575

本文主要是介绍杭电1575-Tr A(矩阵快速幂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1872    Accepted Submission(s): 1382


Problem Description
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
 

Input
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
 

Output
对应每组数据,输出Tr(A^k)%9973。
 

Sample Input
  
2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9
 

Sample Output
  
2 2686
这题是一道纯矩阵快速幂题!
下面我说明下矩阵快速幂的原理(网上搜的见谅):

矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素的o(n)的时间复杂度,降到log(n)。

这里先对原理(主要运用了矩阵乘法的结合律)做下简单形象的介绍:

一般一个矩阵的n次方,我们会通过连乘n-1次来得到它的n次幂。

但做下简单的改进就能减少连乘的次数,方法如下:

把n个矩阵进行两两分组,比如:A*A*A*A*A*A  =>  (A*A)*(A*A)*(A*A)

这样变的好处是,你只需要计算一次A*A,然后将结果(A*A)连乘自己两次就能得到A^6,即(A*A)^3=A^6。算一下发现这次一共乘了3次,少于原来的5次。

其实大家还可以取A^3作为一个基本单位。原理都一样:利用矩阵乘法的结合律,来减少重复计算的次数。

以上都是取一个具体的数来作为最小单位的长度,这样做虽然能够改进效率,但缺陷也是很明显的,取个极限的例子(可能有点不恰当,但基本能说明问题),当n无穷大的时候,你现在所取的长度其实和1没什么区别。所以就需要我们找到一种与n增长速度”相适应“的”单位长度“,那这个长度到底怎么去取呢???这点是我们要思考的问题。

有了以上的知识,我们现在再来看看,到底怎么迅速地求得矩阵的N次幂。

既然要减少重复计算,那么就要充分利用现有的计算结果咯!~怎么充分利用计算结果呢???这里考虑二分的思想。。

大家首先要认识到这一点:任何一个整数N,都能用二进制来表示。。这点大家都应该知道,但其中的内涵真的很深很深(这点笔者感触很深,在文章的最后,我将谈谈我对的感想)!!

计算机处理的是离散的信息,都是以0,1来作为信号的处理的。可想而知二进制在计算机上起着举足轻重的地位。它能将模拟信号转化成数字信号,将原来连续的实际模型,用一个离散的算法模型来解决。  好了,扯得有点多了,不过相信这写对下面的讲解还是有用的。

回头看看矩阵的快速幂问题,我们是不是也能把它离散化呢?比如A^19  =>  (A^16)*(A^2)*(A^1),显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n),不仅这样,因子间也是存在某种联系的,比如A^4能通过(A^2)*(A^2)得到,A^8又能通过(A^4)*(A^4)得到,这点也充分利用了现有的结果作为有利条件。下面举个例子进行说明:

现在要求A^156,而156(10)=10011100(2) 

也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128)  考虑到因子间的联系,我们从二进制10011100中的最右端开始计算到最左端。细节就说到这,下面给核心代码:

核心代码我自己写的,不是网上搜的,而且加注了详细解释:
Matrix matrix_quick_power(matrix a,int k)//重点:矩阵快速幂
{int i;matrix b;memset(b.mat,0,sizeof(b.mat));//初始化for(i=1;i<=n;i++)//这里把b化为单位矩阵,这样如果是第一次乘的话就不会改变a的值b.mat[i][i]=1;while(k)//当k即幂的大小为0时退出循环{if(k&1)//当K为奇数,这里用二进制的“与符号”:&,等同于k%2!=0{b=matrix_mul(a,b);//如果是第一次就乘上单位矩阵不变,不是的话就成上幂的因子数k-=1;}else{a=matrix_mul(a,a);//幂的因子数k>>=1;}}return b;//因为最终k变为0时的前一次k一定为1所以返回b而不是a
}
废话不多说了
下面是这题的AC代码和注解:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
const int MAX=101;
int n;
using namespace std;
typedef struct Matrix
{int mat[MAX][MAX];//定义矩阵
}matrix;
matrix A,B;
Matrix matrix_mul(matrix a,matrix b)//矩阵乘法
{matrix c;memset(c.mat,0,sizeof(c.mat));int i,j,k;for(i=1;i<=n;i++){for(j=1;j<=n;j++){for(k=1;k<=n;k++){c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];c.mat[i][j]%=9973;//每次加完要对9973取模}}}return c;
}
Matrix matrix_quick_power(matrix a,int k)//重点:矩阵快速幂
{int i;matrix b;memset(b.mat,0,sizeof(b.mat));//初始化for(i=1;i<=n;i++)//这里把b化为单位矩阵,这样如果是第一次乘的话就不会改变a的值b.mat[i][i]=1;while(k)//当k即幂的大小为0时退出循环{if(k&1)//当K为奇数,这里用二进制的“与符号”:&,等同于k%2!=0{b=matrix_mul(a,b);//如果是第一次就乘上单位矩阵不变,不是的话就成上幂的因子数k-=1;}else{a=matrix_mul(a,a);//幂的因子数k>>=1;}}return b;//因为最终k变为0时的前一次k一定为1所以返回b而不是a
}
int main()
{int i,j,sum,k,t;cin>>t;while(t--){cin>>n>>k;for(i=1;i<=n;i++){for(j=1;j<=n;j++){cin>>A.mat[i][j];A.mat[i][j]%=9973;//这里也要取模不然矩阵相乘时会溢出}}B=matrix_quick_power(A,k);sum=0;for(i=1;i<=n;i++){sum+=B.mat[i][i];sum%=9973;//同理取模}cout<<sum<<endl;}return 0;
}


这篇关于杭电1575-Tr A(矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978417

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR(重复时间,repetition time)是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言,TR 是施加一个 RF(射频)脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位,主要控制后续脉冲之前的纵向弛豫程度(T1 弛豫),使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简

CentOs7上Mysql快速迁移脚本

因公司业务需要,对原来在/usr/local/mysql/data目录下的数据迁移到/data/local/mysql/mysqlData。 原因是系统盘太小,只有20G,几下就快满了。 参考过几篇文章,基于大神们的思路,我封装成了.sh脚本。 步骤如下: 1) 先修改好/etc/my.cnf,        ##[mysqld]       ##datadir=/data/loc

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

UE5 半透明阴影 快速解决方案

Step 1: 打开该选项 Step 2: 将半透明材质给到模型后,设置光照的Shadow Resolution Scale,越大,阴影的效果越好

快速排序(java代码实现)

简介: 1.采用“分治”的思想,对于一组数据,选择一个基准元素,这里选择中间元素mid 2.通过第一轮扫描,比mid小的元素都在mid左边,比mid大的元素都在mid右边 3.然后使用递归排序这两部分,直到序列中所有数据均有序为止。 public class csdnTest {public static void main(String[] args){int[] arr = {3,