首页 > 试题广场 >

小A的路径

[编程题]小A的路径
小A来到了一个陌生的城镇，这个城镇与其它城镇之间构成了集群。城镇之间的路径都是单向的，而小A每一天都能由一个城镇走到另外一个城镇。小A将会连续走k天，直到抵达某个城镇。也许他并不能走到这个城镇，那么可以认为不存在这样的路径，也就是路径数为0。否则就会有若干条路径可以抵达某个城镇。现在他想知道，如果他从给定某个城市出发，k天之后到达其它城镇的路径的总和是多少。数据不保证没有重边，也就是说可能每一天从一个城镇到另外一个城镇之间会有多条路径。路径总和可能会非常大，对答案模上1000000007。

输入描述:


输出描述:
示例1

输入

4 5 2 1
1 2
1 3
2 3
4 1
3 4

输出

2

说明

经过2天，小A可以走到3号城镇或者4号城镇，到3号城镇的路径有一条是1-2-3，到4号城镇的路径也是一条是1-3-4，共计有两条路径。

备注:
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

枚举
难度：
0条回答 13浏览

热门推荐

相关试题

小A的路径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号