[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂

2023-12-07 07:18

本文主要是介绍[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

可以发现鱼的周期 T = 2, 3, 4;

lcm (2, 3, 4) = 12;

所以当前时刻可以通行的邻接矩阵以12为周期出现

预处理出12个矩阵G[12] 然后全部乘起来存入Tmp

最后答案矩阵为 (Tmp^12) * G1 * ... * Gk%12 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN 50
#define MAXM 50
#define MAXF 20
typedef int LL;
struct Maxtrix{  int n, m;  LL A[MAXN+10][MAXN+10];  
}E, Z;
int n, m, ST, ED, K, Fish;
const int p = 10000;
int way[MAXF][5];
Maxtrix Map, G[12], Tmp;
void init(Maxtrix &X)
{X.n = X.m = 0;memset(X.A, 0, sizeof(X.A));
}
void Get_E()
{E.n = E.m = MAXN;for(int i = 0; i < E.n; i++) E.A[i][i] = 1;
}
Maxtrix add(Maxtrix AA, Maxtrix BB)
{Maxtrix D; D = AA;for(int i = 0; i < AA.n; i++)for(int j = 0; j < AA.m; j++){D.A[i][j] += BB.A[i][j];D.A[i][j] %= p;}return D;
}
Maxtrix mul(Maxtrix AA, Maxtrix BB)
{Maxtrix D;init(D);D.n = AA.n;D.m = BB.m;for(int i = 0; i < AA.n; i++)for(int j = 0; j < BB.n; j++)for(int k = 0; k < BB.m; k++){D.A[i][k] += (AA.A[i][j] * BB.A[j][k]) % p;D.A[i][k] %= p;}return D;
}
Maxtrix pow_mod(Maxtrix &A, int k)
{Maxtrix ans = E, t = A;ans.n = A.n;ans.m = A.m;while(k){if(k & 1)ans = mul(ans, t);t = mul(t, t);k >>= 1;}return ans;
}
void Build()
{for(int tim = 0; tim < 12; tim++){G[tim] = Map;for(int f = 0; f < Fish; f++){int u = way[f][tim % way[f][4]];for(int v = 0; v < n; v++) {if(tim) G[tim-1].A[v][u] = 0;G[tim].A[u][v] = 0;}}}
}
int main()
{Get_E();scanf("%d%d%d%d%d", &n, &m, &ST, &ED, &K);Map.n = Map.m = E.m = E.n = n;Tmp = E;for(int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);Map.A[u][v] = Map.A[v][u] = 1;}scanf("%d", &Fish);for(int i = 0; i < Fish; i++){scanf("%d", &way[i][4]);for(int j = 0; j < way[i][4]; j++) scanf("%d", &way[i][j]);}Build();for(int i = 0; i < 12; i++) Tmp = mul(Tmp, G[i]);Tmp = pow_mod(Tmp, K / 12);K %= 12;for(int i = 0; i < K; i++) Tmp = mul(Tmp, G[i]);printf("%d", Tmp.A[ST][ED]);
}


这篇关于[BZOJ1898] Swamp 沼泽鳄鱼 矩阵快速幂的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

使用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渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析