P4159 [SCOI2009]迷路

    • 239通过
    • 339提交
  • 题目提供者 noip 毒瘤
  • 评测方式 云端评测
  • 标签 枚举,暴力 矩阵乘法 邻接矩阵 各省省选 2009 四川
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    windy在有向图中迷路了。 该有向图有 N 个节点,windy从节点 0 出发,他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图,你能告诉windy总共有多少种不同的路径吗? 注意:windy不能在某个节点逗留,且通过某有向边的时间严格为给定的时间。

    输入输出格式

    输入格式:

    第一行包含两个整数,N T。 接下来有 N 行,每行一个长度为 N 的字符串。 第i行第j列为'0'表示从节点i到节点j没有边。 为'1'到'9'表示从节点i到节点j需要耗费的时间。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2 2
    11
    00
    输出样例#1: 复制
    1
    
    
    输入样例#2: 复制
    5 30
    12045
    07105
    47805
    12024
    12345
    
    输出样例#2: 复制
    852

    说明

    【样例解释一】

    0->0->1

    【数据范围】

    30%的数据,满足 2 <= N <= 5 ; 1 <= T <= 30 。

    100%的数据,满足 2 <= N <= 10 ; 1 <= T <= 1000000000 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。