algorithm - 了解解决此问题的更快方法？

Question

问题陈述在 problem 给出如下:-

N students are bored in computer class so they watch funny video clips on YouTube.

The site contains K popular clips, numbered 1 through N. When a video clip is watched, a list of similar video clips is displayed on the side.

Every student picks a video clip from the main page and starts watching it. After exactly one minute every student gets bored of his or her video clip, so he opens the first video clip from the list of similar clips on the side (even if he already watched that clip).

Write a program that determines for each student which video clip he will be watching during the M-th minute of the class.

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

但我在互联网上找到了一种更快的方法来执行此操作，因为它是一个未记录的代码，而且我是一个新手，我无法弄清楚下面的代码中发生了什么。

    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 度，你将得到一个转换矩阵，显示如果你从视频 开始，你将在第 m 分钟观看哪个视频>我。这也解释了为什么解法的作者在读完M的输入后要减1。