HDU - 4965 - Fast Matrix Calculation(矩阵快速幂)

2024-02-11 02:18

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

题目链接:https://cn.vjudge.net/problem/HDU-4965

思路:正常的矩阵A*B之后得到1000*1000的矩阵,在之后的矩阵乘法中就会爆掉,所以根据矩阵乘法结合律改变下形式:(A*B)^{n*n}=A*(B*A)^{n*n-1}*BB*A是一个6*6的矩阵,这样就可以愉快的矩阵快速幂了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int MAXN = 6;
const int MOD = 6;
int n, k;
struct Matrix
{ll m[MAXN][MAXN];void init(int x){memset(m, 0, sizeof(m));for(int i = 0; i < MAXN; i++){m[i][i] = x;}}Matrix operator * (const Matrix &a) const{Matrix res;res.init(0);for(int i = 0; i < MAXN; i++)for(int j = 0; j < MAXN; j++)for(int k = 0; k < MAXN; k++)res.m[i][j] = (res.m[i][j] + (m[i][k] * a.m[k][j]) % MOD) % MOD;return res;}
};Matrix quickPow(Matrix x, ll p)
{Matrix res;res.init(1);x = x * res;while(p){if(p & 1) res = res * x;p >>= 1;x = x * x;}return res;
}
ll a[N][N], b[N][N], p[N][N], d[N][N];
Matrix c, x;
void init()
{c.init(0);memset(p, 0, sizeof(p));memset(d, 0, sizeof(d));for(int i = 0; i < n; i++)for(int j = 0; j < k; j++)scanf("%lld",&a[i][j]);for(int i = 0; i < k; i++)for(int j = 0; j < n; j++)scanf("%lld",&b[i][j]);for(int i = 0; i < k; i++)for(int j = 0; j < k; j++)for(int g = 0; g < n; g++)c.m[i][j] = c.m[i][j] + b[i][g] * a[g][j];x = quickPow(c, n * n - 1);for(int i = 0; i < n; i++)for(int j = 0; j < k; j++)for(int g = 0; g < k; g++)p[i][j] = p[i][j] + a[i][g] * x.m[g][j];for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)for(int g = 0; g < k; g++)d[i][j] = d[i][j] + p[i][g] * b[g][j];
}int main()
{while(~scanf("%d%d",&n,&k) && n+k){init();ll ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)ans += d[i][j] % MOD;printf("%lld\n",ans);}return 0;
}

 

这篇关于HDU - 4965 - Fast Matrix Calculation(矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/698586

相关文章

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

SpringBoot快速搭建TCP服务端和客户端全过程

《SpringBoot快速搭建TCP服务端和客户端全过程》:本文主要介绍SpringBoot快速搭建TCP服务端和客户端全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录TCPServerTCPClient总结由于工作需要,研究了SpringBoot搭建TCP通信的过程

一文教你Python如何快速精准抓取网页数据

《一文教你Python如何快速精准抓取网页数据》这篇文章主要为大家详细介绍了如何利用Python实现快速精准抓取网页数据,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录1. 准备工作2. 基础爬虫实现3. 高级功能扩展3.1 抓取文章详情3.2 保存数据到文件4. 完整示例

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作,重启的时候,内核启动中止于Panic状态,该怎么解决这个问题呢?下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase