Nyoj 302 星际旅行[矩阵乘法求两点k步方案数]

2024-06-07 03:38

本文主要是介绍Nyoj 302 星际旅行[矩阵乘法求两点k步方案数],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=302

题目意思。。n*m的矩阵。。每个元素代表一个星球,每个元素的值为所属国家,也就是每个星球属于一个国家。。每个相邻(上下左右)的星球有一个航道。每个国家的任意的两个星球都有星际之门。。。。。问,从(1,1)星球到(n,m)星球的方案数。。。相同的方案为走过的星球顺序相同。。。。。

处理一下图就是很裸的问题。。。

处理图的方式有很多中。。。

我的方法为,把二维矩阵散列到一维上。。然后,两两判断是否有通路。。然后处理到邻接矩阵中。。。。直接矩阵乘法就好。。。

Code:

 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
const int N = 105;
const LL mod = 1000007;
struct Matrix
{int n;LL a[N][N];Matrix(){memset(a, 0, sizeof(a));}
} ans, A;
int node[N], n;
int m, p;bool Judge(int x, int y)
{if(x - n == y) return true;else if(x + n == y) return true;else if(x - 1 == y && y % n != 0) return true;else if(x + 1 == y && x % n != 0) return true;else return false;
}Matrix operator * (Matrix a, Matrix b)
{Matrix tmpans;tmpans.n = a.n;for(int i = 1; i <= a.n; i ++){for(int j = 1; j <= a.n; j ++){for(int k = 1; k <= a.n; k ++)tmpans.a[i][j] = (tmpans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
//            printf("k = %d\n", tmpans.a[i][j]);}}return tmpans;
}void power(int k)
{while(k){if(k & 1) ans = ans * A;A = A * A;k = k >> 1;}
}int main()
{
//    freopen("1.txt", "r", stdin);int T;cin >> T;while(T --){cin >> n >> m >> p;for(int i = 0; i < m; i ++){for(int j = 1; j <= n; j ++){cin >> node[i * n + j];}}for(int i = 1; i <= m * n; i ++){for(int j = 1; j <= m * n; j ++){A.a[i][j] = 0; ans.a[i][j] = 0;if(i == j) continue;if(node[i] == node[j]) A.a[i][j] = 1;else if(Judge(i, j)){A.a[i][j] = 1;}}ans.a[i][i] = 1;}ans.n = n * m; A.n = n * m;power(p);printf("%lld\n", ans.a[1][n * m] % mod);}return 0;
}

表示NYOJ上关于矩阵的题目数据的还是很强大的。。。。

这篇关于Nyoj 302 星际旅行[矩阵乘法求两点k步方案数]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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 三种配置方式

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

MySQL分表自动化创建的实现方案

《MySQL分表自动化创建的实现方案》在数据库应用场景中,随着数据量的不断增长,单表存储数据可能会面临性能瓶颈,例如查询、插入、更新等操作的效率会逐渐降低,分表是一种有效的优化策略,它将数据分散存储在... 目录一、项目目的二、实现过程(一)mysql 事件调度器结合存储过程方式1. 开启事件调度器2. 创