HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数

2024-06-15 11:58

本文主要是介绍HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:求A经过K个点到B方案数

1个0 1 的矩阵 A

a[i][j] = 1 表示i 到 j可达 或者说 i 到 j 有1条路 或者说i到j经过一个点的方案数 路可以重复走

 

而A2 = A* A

a[i][j] 的含义是

从i到j经过2个点的方案数

A的k次方 A[i,j]代表 i到j走k步的方案有a[i][j]

T组询问 x y z 快速幂求出A矩阵的y次 然后输出A[x][y]

#include <cstdio>
#include <cstring>
const int mod = 1000;
const int maxn = 22;
struct Mat
{int a[maxn][maxn];
};
Mat A, B, C, D;
int n, m;
Mat get(Mat x, Mat y)
{Mat z;memset(z.a, 0, sizeof(z.a));for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)for(int k = 1; k <= n; k++){z.a[i][j] += x.a[i][k]*y.a[k][j];z.a[i][j] %= mod;}return z;
}
void Mat_pow(int n)
{//puts("s");if(n <= 0)return;while(n){if(n&1)B = get(A, B);A = get(A, A);n >>= 1;}
}
int main()
{while(scanf("%d %d", &n, &m) && (n+m)){memset(D.a, 0, sizeof(D.a));memset(C.a, 0, sizeof(C.a));while(m--){int u, v;scanf("%d %d", &u, &v);u++;v++;D.a[u][v] = 1;}for(int i = 1;  i<= n; i++)C.a[i][i] = 1;int T;scanf("%d", &T);while(T--){int u, v, w;scanf("%d %d %d", &u, &v, &w);			u++;v++;B = C;A = D;Mat_pow(w);printf("%d\n", B.a[u][v]);}}return 0;
}


 

这篇关于HDU 2157 How many ways?? 矩阵快速幂求A经过K个点到B方案数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

springboot security快速使用示例详解

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

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

Python实现html转png的完美方案介绍

《Python实现html转png的完美方案介绍》这篇文章主要为大家详细介绍了如何使用Python实现html转png功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 1.增强稳定性与错误处理建议使用三层异常捕获结构:try: with sync_playwright(

Java使用多线程处理未知任务数的方案介绍

《Java使用多线程处理未知任务数的方案介绍》这篇文章主要为大家详细介绍了Java如何使用多线程实现处理未知任务数,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 知道任务个数,你可以定义好线程数规则,生成线程数去跑代码说明:1.虚拟线程池:使用 Executors.newVir

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回(flashback)功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回(flashb

Android App安装列表获取方法(实践方案)

《AndroidApp安装列表获取方法(实践方案)》文章介绍了Android11及以上版本获取应用列表的方案调整,包括权限配置、白名单配置和action配置三种方式,并提供了相应的Java和Kotl... 目录前言实现方案         方案概述一、 androidManifest 三种配置方式

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

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

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

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