逆向列表拼接 Python 优化（USACO 2020 年 2 月青铜问题 3“Swapity Swap”）
我正在尝试解决一个涉及反转列表拼接的问题，但我在测试用例的时间限制方面遇到了问题，即 4 秒。问题：
Farmer John 的 N 头奶牛 (1?N?100) 排成一排。左边的第 i 头奶牛有标签 i，每 1?i?N。农夫约翰为奶牛制定了一个新的晨练程序。他告诉他们准确地重复以下两步过程 K (1?K?1000000000) 次：
当前在位置 A1…A2 的奶牛从左边的顺序颠倒了它们的顺序 (1?A1<A2?N)。然后，当前在位置 B1…B2 从左边开始的奶牛的顺序颠倒它们的顺序 (1?B1<B2?N)。在奶牛重复这个过程正好 K 次后，请输出从左边开始每 1?i?N 的第 i 头奶牛的标签。
评分：测试用例 2-3 满足 K?100。测试用例 4-13 不满足其他约束。
INPUT FORMAT（文件swap.in）：输入的第一行包含N和K，第二行包含A1和A2，第三行包含B1和B2。
OUTPUT FORMAT（文件swap.out）：在输出的第i行，在例程结束时从左边打印第i头牛的标签。
样品输入：
7 2
2 5
3 7
样品输出：
1
2
4
3
5
7
6
最初，奶牛的顺序是 [1,2,3,4,5,6,7] 从左到右。在过程的第一步之后，顺序是[1,5,4,3,2,6,7]。经过第二步的过程，顺序是[1,5,7,6,2,3,4]。第二次重复这两个步骤会产生样本的输出。
理论上，您可以通过找到程序重复的点，然后模拟相反的k % frequency时间来解决这个问题，其中模拟的次数frequency是唯一的。但我的问题是，当输入是：
100 1000000000
1 94
2 98
我的程序需要 100 多秒才能运行。这个输入特别耗时，因为它运行的迭代次数最多，而且frequency非常高。
当前代码：
fin = open("swap.in", 'r')
line = fin.readline().strip().split()
n = int(line[0])
k = int(line[1])
nums = [[int(x)-1 for x in fin.readline().strip().split()]for i in range(2)]
fin.close()
repeated = []
cows = [i for i in range(1, n+1)]
repeat = False
while not repeat:
for i in nums:
cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1])
if cows[i[0]:i[1]+1] in repeated :
frequency = len(repeated)-1
repeat = True
repeated.append(cows[i[0]:i[1]+1])
cows = [i for i in range(1, n+1)]
for _ in range(k%frequency):
for i in nums:
cows[i[0]:i[1]+1] = reversed(cows[i[0]:i[1]+1])
fout = open("swap.out", 'w')
for i in cows:
fout.write(str(i) + "\n")
fout.close()
如果有人知道解决此问题的方法，请发布答案。如果有什么不清楚的可以评论。
回答
让我们先谈谈我们如何从数学上解决这个问题，然后以编程的方式找出一个解决方案。
假设每个位置的奶牛由变量 表示Pi.j，其中i是奶牛索引，j是交换迭代。这些变量每个都包含一个与那头奶牛的唯一 id 相对应的整数。此外，为简单起见，我们将在每次迭代中只考虑一个反转操作，并在稍后扩展以包括这两个操作。
从 P0.0（第 0 次位置，第 0 次迭代）开始，我们想开始定义一些方程，以便在下一次迭代中为我们提供给定位置的奶牛。如果母牛在反转区域之外，这是微不足道的；母牛不变。如果它在反转区域内，我们将要根据反转区域的端点计算新奶牛的先前位置。明确：
- 如果在反转区域之外：
Pi.(j+1) = Pi.j - else:
Pi.(j+1) = P(e1+e2-i).j, 其中e1和e2是区域端点
现在，根据我们的规则，我们实际上可以写出一个方程组：
P0.b = 1 * P0.a
P1.b = 1 * P1.a
...
P4.b = 1 * P7.a // reversal region starts
P5.b = 1 * P6.a
...
从这里，我们可以将这些问题系统转换为转换矩阵MA，当乘以牛 id 向量时，将在反转后返回一个新的牛 id 向量。
这就是事情变得有趣的地方。我们可以对另一个反转区域做同样的事情，制作第二个矩阵MB，然后将其乘以MA得到一个整体矩阵M，该矩阵将两个反转合二为一。从这里，我们可以将矩阵提升到幂K（迭代次数），对于单个矩阵，它将在所有反转发生后计算每个位置的奶牛。
现在，在这一点上，您可能会质疑这种方法的性能——毕竟，我们正在将 100x100 矩阵K提升到109! 好吧，我们有一些技巧可以使这更快。首先，请注意，一头母牛，任何一头母牛，我们都可以通过混洗所有反转操作进行逻辑推理并确定其结束位置，而无需知道其他母牛在哪里/哪些其他母牛是哪一头。
这意味着对于任何给定时间的任何给定位置，该位置的奶牛可以由任何其他迭代中的另一个位置精确定义（例如，P12.7（位置 12 迭代 7）可以通过了解相应位置的奶牛来准确确定在迭代中，例如，迭代 5-P8.5）。
这很有用，因为这意味着我们矩阵的每一行都将恰好有一个非零元素，并且该元素将具有1（方程组1中的系数）的值，因此我们实际上可以将我们的 100x100 矩阵压缩为一个数组仅 100 个值说明每行的哪一列包含1.
太好了，我们可以O(n^2)使用这个技巧及时乘以矩阵。好吧，我们实际上还可以做得更好——我们实际上可以O(n)及时乘以这些。对于每一个“行” R（只包含列索引，I该的1值），在第一矩阵，看看I在我们的第二个矩阵列，第并获得其价值C。将我们R'在输出矩阵中的相应行分配给 equal C。
所以我们可以在大约 100 个逻辑步骤中将这些矩阵相乘，但我们需要将这个矩阵提高到Kth 次方，可以达到109。我们刚刚从我们的工作中消除了 100 的因素，只是为了把它加回来！嗯，不完全是。有“由平方幂”，在这里我们巧妙地错开乘以反复平方的结果，来计算矩阵幂众所周知的方法调用，M^K在log(K)迭代/步骤。我不会在这里详细介绍，因为它广为人知且有据可查。
总的来说，这让我们处于 O(N log K) 时间，还不错！
更新：这是解决问题的功能代码。
P0.b = 1 * P0.a
P1.b = 1 * P1.a
...
P4.b = 1 * P7.a // reversal region starts
P5.b = 1 * P6.a
...
在做了一些timeit用于number=100迭代的基准测试后，这些是我的发现（以秒为单位的时间，越小越好）：
contributor | time (sec)
------------------------------
blhsing | 7.857691
Michael Szczesny | 5.076418
(mine) | 0.013314
因此，Michael 改进了 blhsing 的解决方案，在我的机器上运行速度提高了约 1.5 倍，而我的解决方案的运行速度比 Michael 的解决方案快了约 381 倍，平均每次运行大约需要千分之一秒。
更新 2：正如在这个答案的评论中提到的，上面的解决方案仍然可以扩展K，所以最终它会变得棘手，而且这个问题似乎会发出重复的模式——我们当然可以利用它吗？嗯，是的，事实上我们可以。
诀窍是，在这些奶牛达到我们以前见过的某个先前状态之前，我们可以通过多种方式对其进行置换，然后从那里形成一个无限循环。事实上，由于手头问题的简单性，在我们回到之前的状态（实际上是我们的起始状态，因为访问任何其他母牛排列而不先访问我们的起始状态）之前，通常会进行相对较少的洗牌/反转state 意味着有两个不同的状态可以转换到所述状态，这不可能 - 我们有我们的方程系统告诉我们否则）。
因此，如果找到牛洗牌/逆转开始重复的这个神奇数字，我们需要做什么，并使用它来减少指数（在我们的矩阵求幂中）从K到K mod MAGIC。我们实际上将把这个数字称为转移矩阵的乘法阶数。首先，请注意可能有不止一个奶牛轮换位置，每个周期都重复一段时间。4 头奶牛的子集可以每 4 次迭代循环一次位置，而 3 头奶牛的另一个子集每 3 次迭代循环一次，这意味着 7 头奶牛一起每 12 次迭代重复它们的起始配置。
更一般地，我们需要找到牛洗牌的每个独立周期，得到它们的长度，并找到这些周期的最小公倍数 (LCM)。一旦我们有了它，就用那个Kmod 把我们的矩阵提升到那个新值。这样做的示例代码：
def matmul(p, q):
return [q[I] for I in p]
def exp(m, e):
if e == 1:
return m
result = exp(matmul(m, m), e // 2)
if e % 2:
result = matmul(m, result)
return result
def solve(n, k, a1, a2, b1, b2):
a1, a2, b1, b2 = a1-1, a2-1, b1-1, b2-1
cows = list(range(1, n+1))
ma = [a1 + a2 - x if a1 <= x <= a2 else x for x in range(n)]
mb = [b1 + b2 - x if b1 <= x <= b2 else x for x in range(n)]
m0 = matmul(mb, ma)
mk = exp(m0, k)
return [cows[i] for i in mk]