做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2927. -- 「一本通 6.5 练习 3」迷路

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

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

原题来自:SCOI 2009

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

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

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

输入

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

输出

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

提示

样例输入 1

2 2
11
00

样例输出 1

1

样例说明 1

0→0→10 o 0 o 1001

样例输入 2

5 30
12045
07105
47805
12024
12345

样例输出 2

852

对于 30%30\%30% 的数据,满足 2≤N≤5,1≤T≤302le Nle 5,1le Tle 302N5,1T30
对于 100%100\%100% 的数据,满足 2≤N≤10,1≤T≤1092le Nle 10,1le Tle 10^92N10,1T109

标签

[上一题][提交][讨论版][状态][下一题]