用于计算可能的路线数量的矩阵求幂

Question

最近我在 Iarcs 网站上遇到了 this 问题。这是问题陈述：

It is well known that the routing algorithm used on the Internet is highly non-optimal. A "hop", in Internet jargon, is a pair of nodes that are directly connected - by a cable or a microwave link or whatever. The number of hops that a packet may take in going from one node to another may be far more than the minimum required.

But the routing algorithm used by the Siruseri Network company is worse. Here, a packet sent from one node to another could even go through the same node twice or even traverse the same hop twice before it eventually finds its way to its destination. Sometimes a packet even goes through the destination more than once before it is considered "delivered". Suppose the network in Siruseri consisted of the following nodes and cables: Figure

There are 5 nodes and 8 cable links. Note that a pair of nodes may be connected by more than one link. These are considered to be different hops. All links are bidirectional. A packet from node 1 to node 5 may, for example, travel as follows: 1 to 2, 2 to 1, 1 to 3, 3 to 2, 2 to 1, 1 to 4, 4 to 5, 5 to 4, 4 to 5. This routing is of length 9 (the number of hops is the length of a given routing). We are interested in counting the number of different routings from a given source to a target that are of a given length.

For example, the number of routings from 1 to 2 of length 3 are 7. They are as follows (separated by ;): 1 to 2, 2 to 1 and 1 to 2; 1 to 3, 3 to 1 and 1 to 2; 1 to 4, 4 to 1 and 1 to 2; 1 to 5, 5 to 1 and 1 to 2; 1 to 4, 4 to 3 (via the left cable) and 3 to 2; 1 to 4, 4 to 3 (via the right cable) and 3 to 2; 1 to 2, 2 to 3 and 3 to 2.

You will be given a description of the network at Siruseri as well as a source, a target and the number of hops, and your task is to determine the number of routings from the source to the target which have the given number of hops. The answer is to be reported modulo 42373.

因此，正如在 this 线程上讨论的那样，解决方案是计算给定矩阵的 k 次方，其中 k 是给定的路由数。

这里我也是这样做的：

#include <iostream>
#include <vector>

std::vector<std::vector<int> >MatrixMultiplication(std::vector<std::vector<int> >matrix1,std::vector<std::vector<int> >matrix2,int n){
    std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                retMatrix[i][j] = retMatrix[i][j] + matrix1[i][k] * matrix2[k][j];
            }
        }
    }

    return retMatrix;
}

std::vector<std::vector<int> >MatrixExponentiation(std::vector<std::vector<int> >matrix,int n,int power){
    if(power == 0 || power == 1){
        return matrix;
    }

    if(power%2 == 0){
        return MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,power/2);
    }else{
        return MatrixMultiplication(matrix,MatrixExponentiation(MatrixMultiplication(matrix,matrix,n),n,(power-1)/2),n);
    }
}

int main (int argc, char const* argv[])
{
    int n;
    std::cin >> n;
    std::vector<std::vector<int> >matrix(n,std::vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            std::cin >> matrix[i][j];
        }
    }
    int i ,j ,power;
    std::cin >> i >> j >> power;
    std::vector<std::vector<int> >retMax(n,std::vector<int>(n));
    retMax = MatrixExponentiation(matrix,n,power);
    std::cout << matrix[i-1][j-1] << std::endl;
    return 0;
}

但是即使示例案例的输出也不匹配，我是否遗漏了什么，或者我必须尝试另一种方法来解决这个问题？

Edit ：正如@grigor 建议的那样，我将 power == 0 的代码更改为 return 单位矩阵，但代码仍然产生错误的输出，

if(power == 0){
        std::vector<std::vector<int> >retMatrix(n,std::vector<int>(n));
        for(int i=0;i<n;i++){
            retMatrix[i][i] = 1;
        }
        return retMatrix;
    }

注意：我还没有写模数的代码，你认为它对示例测试用例有影响吗？

Answer 1

如果 power == 0 你应该 return 单位矩阵，而不是实际矩阵。

Answer 2

我认为你只是打印出了错误的值，更改：

std::cout << matrix[i-1][j-1] << std::endl;

至

std::cout << retMax [i-1][j-1] << std::endl;

用于计算可能的路线数量的矩阵求幂

Matrix Exponentiation for calculating number of routes possible

c++

algorithm

vector

matrix-multiplication