问题描述
路径的长度"是路径中的边数.
'Length' of a path is the number of edges in the path.
给定一个源顶点和一个目标顶点，我想找到路径数从源顶点到目标顶点给定长度 k.
Given a source and a destination vertex, I want to find the number of paths form the source vertex to the destination vertex of given length k.
我们可以随意访问每个顶点，所以如果从 a 到 b 的路径是这样的:a ->c->b->c->b 它被认为是有效的.这意味着可以有循环，我们可以多次经过目的地.
We can visit each vertex as many times as we want, so if a path from a to b goes like this: a -> c -> b -> c -> b it is considered valid. This means there can be cycles and we can go through the destination more than once.
两个顶点可以通过多条边连接.因此，如果顶点 a 和顶点 b 由两条边连接，那么路径 , a ->;b 通过边缘 1 和 a ->;b 通过边缘 2 被认为是不同的.
Two vertices can be connected by more than one edge. So if vertex a an vertex b are connected by two edges, then the paths , a -> b via edge 1 and a -> b via edge 2 are considered different.
顶点数 N 为 <= 70，路径长度 K 为 <= 10^9.
Number of vertices N is <= 70, and K, the length of the path, is <= 10^9.
由于答案可能很大，所以要以某个数为模.
As the answer can be very large, it is to be reported modulo some number.
这是我目前的想法:
我们可以使用 breadth-first-search 而不将任何顶点标记为已访问，在每次迭代，我们都会跟踪该路径所需的边数n_e"，以及路径中每条边所具有的重复边数的productp".
We can use breadth-first-search without marking any vertices as visited, at each iteration, we keep track of the number of edges 'n_e' we required for that path and product 'p' of the number of duplicate edges each edge in our path has.
如果 n_e 大于 k，搜索应该终止，如果我们到达目的地 n_e等于 k，我们终止搜索并添加 p 计算路径数.
The search search should terminate if the n_e is greater than k, if we ever reach the destination with n_eequal to k, we terminate the search and add p to out count of number of paths.
我认为我们可以使用深度优先搜索而不是广度优先搜索，因为我们不需要最短路径，并且在广度优先搜索中使用的 Q 的大小可能还不够.
I think it we could use a depth-first-search instead of breadth first search, as we do not need the shortest path and the size of Q used in breadth first search might not be enough.
我正在考虑的第二个算法类似于 Floyd Warshall 算法 使用 这种 方法.只有我们不需要最短路径，所以我不确定这是否正确.
The second algorithm i have am thinking about, is something similar to Floyd Warshall's Algorithm using this approach . Only we dont need a shortest path, so i am not sure this is correct.
我的第一个算法遇到的问题是K"可以达到 1000000000，这意味着我的搜索将一直运行到它有 10^9 条边并且 n_e 边数将在每个级别仅增加 1，这会很慢，我不确定它是否会因大量输入而终止.
The problem I have with my first algorithm is that 'K' can be upto 1000000000 and that means my search will run until it has 10^9 edges and n_e the edge count will be incremented by just 1 at each level, which will be very slow, and I am not sure it will ever terminate for large inputs.
所以我需要一种不同的方法来解决这个问题；任何帮助将不胜感激.
So I need a different approach to solve this problem; any help would be greatly appreciated.
推荐答案
所以，这是我记得的一个漂亮的图论技巧.
So, here's a nifty graph theory trick that I remember for this one.
制作一个邻接矩阵A.其中，如果 i 和 j 之间有边，则 A[i][j] 为 1，否则为 0.
Make an adjacency matrix A. where A[i][j] is 1 if there is an edge between i and j, and 0 otherwise.
那么，i和j之间长度为k的路径数就是[i][j] A^k 的条目.
Then, the number of paths of length k between i and j is just the [i][j] entry of A^k.
所以，为了解决这个问题，构建 A 并使用矩阵乘法构造 A^k(这里适用于求幂的常用技巧).然后只需查找必要的条目.
So, to solve the problem, build A and construct A^k using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.
嗯，你需要在矩阵乘法中进行模运算以避免溢出问题，但这是一个小得多的细节.
Well, you need to do the modular arithmetic inside the matrix multiplication to avoid overflow issues, but that's a much smaller detail.