P4159 [SCOI2009] 迷路(矩阵快速幂,两点路径为k的方案数)

2024-04-15 23:08

本文主要是介绍P4159 [SCOI2009] 迷路(矩阵快速幂,两点路径为k的方案数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

思路:
具体参考https://www.luogu.com.cn/blog/qq-2056188203/mi-lu-scoi2009-ti-xie

简而言之,就是如果权值为1,要求两点之间经过 k k k条边的路径方案数,只要将邻接矩阵进行 k k k次方就好了。
本题权重为1~9,我们将每个点拆成10个点,两个点边权就通过拆成的点建边来表示,这样就成了权值为1的邻接矩阵形式了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;
const int maxn = 107;
const int mod = 2009;
int n,t;struct Matrix {int Ma[maxn][maxn];void clear() {memset(Ma,0,sizeof(Ma));}
}A;Matrix Mul(Matrix m1,Matrix m2) {Matrix now;now.clear();for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {for(int k = 1;k <= n;k++) {now.Ma[i][j] = (now.Ma[i][j] + m1.Ma[i][k] * m2.Ma[k][j]) % mod;}}}return now;
}Matrix Qpow(Matrix a,int b) {Matrix now;now.clear();for(int i = 1;i <= n;i++) now.Ma[i][i] = 1;while(b) {if(b & 1) now = Mul(now,a);a = Mul(a, a);b >>= 1;}return now;
}int f(int i,int j) {return (i - 1) * 10 + j;
}int main() {scanf("%d%d",&n,&t);int N = n;n *= 10;for(int i = 1;i <= N;i++) {for(int j = 1;j < 10;j++) {A.Ma[f(i,j)][f(i,j + 1)] = 1;}for(int j = 1;j <= N;j++) {int x;scanf("%1d",&x);if(x) {A.Ma[f(i,x)][f(j,1)] = 1;}}}A = Qpow(A, t);printf("%d\n",A.Ma[f(1,1)][f(N,1)]);return 0;
}

这篇关于P4159 [SCOI2009] 迷路(矩阵快速幂,两点路径为k的方案数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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、查看提

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

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.由快

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想