小灵的奇妙上学之旅(HARD)
题目大意
给出一个NNN个结点MMM条边的有向图，并且保证只会存在由前面顶点到达后面的边。求从1号顶点到达NNN号顶点所有的走法。
思路解析
范围由一开始的n≤50n \leq50n≤50开到了n≤1000n \leq 1000n≤1000，所以暴力枚举肯定行不通，但是我们可以发现一件事，在这个有向图当中，前面的顶点只会前往后面的顶点，那么他是不会返回的。
如果我们计算出了第iii号顶点的路径总数，那么pospospos号顶点可以前往pos2pos2pos2号顶点的话，那么我们是不是可以认为，pos2pos2pos2号顶点的方案总数，一定包含pospospos号顶点的方案总数，因此我们就可以列出状态转移方程。
IFIFIF $ G[pos][i] == pos2$ dp[pos2]+=dp[pos]dp[pos2] += dp[pos]dp[pos2]+=dp[pos]
代码演示
