题目:「一本通 6.5 练习 3」迷路

2024-03-23 16:12
文章标签 题目 练习 一本 6.5 迷路

本文主要是介绍题目:「一本通 6.5 练习 3」迷路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述
原题来自:SCOI 2009

Windy 在有向图中迷路了。 该有向图有 N 个节点,Windy 从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。

现在给出该有向图,你能告诉 Windy 总共有多少种不同的路径吗?

注意:Windy 不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。

输入输出格式
输入格式:
第一行包含两个整数,N,T;
接下来有 N 行,每行一个长度为 N 的字符串。第 i 行第 j 列为 0 表示从节点 i 到节点 j 没有边,为 19 表示从节点 i 到节点 j 需要耗费的时间。

输出格式:
包含一个整数,可能的路径数,这个数可能很大,只需输出这个数除以 2009 的余数。

输入输出样例
输入样例#1:

2 2
11
00

输出样例#1:

1
#include<bits/stdc++.h>
using namespace std;int n,t;
const long long Mod=2009;struct node {int g[205][205];void clear(){memset(g,0,sizeof g);}
}A;node YunSuan(node x, node y) {node 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.g[i][j]=(now.g[i][j]+x.g[i][k] * y.g[k][j])%Mod;}}}return now;
}void g(node &o){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) o.g[i][j]=1;else o.g[i][j]=0;}}
}
node Power(node a,int b){node now;now.clear();g(now);while(b){if(b&1)now=YunSuan(now,a);a=YunSuan(a,a);b>>=1;}return now;
}int Cheak(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.g[Cheak(i,j)][Cheak(i,j+1)]=1;}for(int j=1;j<=N;j++){int x;scanf("%1d",&x);if(x){A.g[Cheak(i,x)][Cheak(j,1)]=1;}}}A=Power(A,t);printf("%d\n",A.g[1][10*N-9]);
}

这篇关于题目:「一本通 6.5 练习 3」迷路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

【Rust练习】12.枚举

练习题来自:https://practice-zh.course.rs/compound-types/enum.html 1 // 修复错误enum Number {Zero,One,Two,}enum Number1 {Zero = 0,One,Two,}// C语言风格的枚举定义enum Number2 {Zero = 0.0,One = 1.0,Two = 2.0,}fn m

MySql 事务练习

事务(transaction) -- 事务 transaction-- 事务是一组操作的集合,是一个不可分割的工作单位,事务会将所有的操作作为一个整体一起向系统提交或撤销请求-- 事务的操作要么同时成功,要么同时失败-- MySql的事务默认是自动提交的,当执行一个DML语句,MySql会立即自动隐式提交事务-- 常见案例:银行转账-- 逻辑:A给B转账1000:1.查询

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

NGINX轻松管理10万长连接 --- 基于2GB内存的CentOS 6.5 x86-64

转自:http://blog.chinaunix.net/xmlrpc.php?r=blog/article&uid=190176&id=4234854 一 前言 当管理大量连接时,特别是只有少量活跃连接,NGINX有比较好的CPU和RAM利用率,如今是多终端保持在线的时代,更能让NGINX发挥这个优点。本文做一个简单测试,NGINX在一个普通PC虚拟机上维护100k的HTTP

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

014.Python爬虫系列_解析练习

我 的 个 人 主 页:👉👉 失心疯的个人主页 👈👈 入 门 教 程 推 荐 :👉👉 Python零基础入门教程合集 👈👈 虚 拟 环 境 搭 建 :👉👉 Python项目虚拟环境(超详细讲解) 👈👈 PyQt5 系 列 教 程:👉👉 Python GUI(PyQt5)文章合集 👈👈 Oracle数据库教程:👉👉 Oracle数据库文章合集 👈👈 优

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que