[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

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

利用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,

快速幂(基础算法)

文章目录 目的基本例子暴力代码思路讲解优化(即快速幂)位运算写法(终极优化) 目的 减小时间复杂度 基本例子 a的b次方,最后取模 暴力代码 long long ans=1;long long a,b;for(long long i=1;i<=b;i++){ans*=a;}ans%=c; 当数据大的时候就不行了 思路讲解 3¹⁰=(3²)⁵= 9⁵ =