了解更快的方法来解决这个问题吗？

Question

问题陈述在问题给出，如下所示：

N名学生在计算机课上很无聊，所以他们在YouTube上看有趣的视频剪辑。 该网站包含K个受欢迎的剪辑，编号从1到N。当观看一个视频剪辑时，旁边会显示一个类似视频剪辑的列表。 每个学生都会从主页上挑选一段视频片段，然后开始观看。整整一分钟后，每个学生都厌倦了他或她的视频剪辑，于是他从旁边的类似视频列表中打开了第一个视频剪辑(即使他已经看过该视频)。 编写一个程序，为每个学生确定他将在课堂的第M分钟观看哪个视频剪辑。

现在我知道如何解决这个问题，我们找到路径，如果它包含一个循环。我们用它的周期得到答案。

但我在互联网上找到了一种更快的方法来做到这一点，因为它是一个无文档的代码，而我是一个新手，我无法弄清楚在下面的代码中发生了什么。

    int N = in.nextInt (), K = in.nextInt (), M = in.nextInt () - 1;//Reading input

    int log = Integer.numberOfTrailingZeros (Integer.highestOneBit (M)) + 1;

    int [][] next = new int [K][log + 1];

    int [] start = new int [N];
    for (int i = 0; i < N; i++)
        start [i] = in.nextInt () - 1;

    for (int i = 0; i < K; i++)
        next [i][0] = in.nextInt () - 1;

    for (int i = 1; 1 << i <= M; i++)
        for (int j = 0; j < K; j++)
            next [j][i] = next [next [j][i - 1]][i - 1];

    for (int i = 0; 1 << i <= M; i++)
        if (((1 << i) & M) > 0)
            for (int j = 0; j < N; j++)
                start [j] = next [start [j]][i];

    out.print (start [0] + 1);
    for (int i = 1; i < N; i++)
        out.print (" " + (start [i] + 1)); //writing output

我们怎样才能有效地解决这个问题，而不费心地寻找周期呢？或者上面的代码是如何解决问题的？

Answer 1

这个解通过矩阵的平方来进行幂运算。对于每个视频，相关视频的列表是预先确定的，因此您知道哪个视频是该列表中的第一个。所以，对于每一个视频，你都知道你接下来要看的是哪个视频。

你有一个简单的变换矩阵。在第一行i中，您将有一个1 --在视频索引处，即视频编号i之后的索引处，其余所有元素都为0。取这个矩阵，并将其提升到m-1 - th度，你将得到一个变换矩阵，它显示如果你开始使用视频i，你将在m分钟内观看哪一段视频。这也解释了为什么解决方案的作者在阅读后从M的输入中减去1。

Answer 2

上面的代码忽略了圆锥花序。他使用了一种类似于快速指数的自下而上的动态规划方法。他使用下一个矩阵存储每个学生在1、2、2^2等步骤之后的下一个位置。这是第三次的工作。然后，在第四个for中，他以二进制形式构造M。这样，如果M= 2^3 + 2^0，则可以计算每个学生的位置，先计算2^0分钟后的位置，然后将这个位置指定为基本位置，然后在距新位置2^3分钟后计算该位置。

如果你看一下关于快速指数的信息，你会发现这个O(N log(M))回忆录空间是不必要的，因为只有一个请求，您可以在执行“快速指数”步骤时计算最后的位置。