反转列表拼接 Python 优化（USACO 2020 年 2 月铜题 3 "Swapity Swap"）
Reversing Lists Splices Python Optimization (USACO February 2020 Bronze Question 3 "Swapity Swap")
我正在尝试解决涉及反转列表拼接的问题，但我在测试用例的时间限制方面遇到了问题，该时间限制为 4 秒。问题：
Farmer John的N头奶牛（1≤N≤100）排成一排。从左数第 i 头奶牛的标签为 i，每个 1≤i≤N。
农夫约翰为奶牛制定了新的晨练计划。他让他们重复以下两步过程恰好 K (1≤K≤1000000000) 次：
当前位置A1…A2的奶牛顺序从左倒序（1≤A1
得分：
测试用例2-3满足K≤100。
测试用例 4-13 不满足任何附加约束。
输入格式（文件swap.in）：
输入的第一行是N和K，第二行是A1和A2，第三行是B1和B2。
输出格式（文件swap.out）：
在输出的第 i 行，在 exercise routine 结束时打印左起第 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()
如果有人知道解决这个问题的方法，请post回答。如果有任何不清楚的地方，请发表评论。
让我们先谈谈如何从数学上解决这个问题，然后再以编程方式解决这个问题。
假设每个位置的奶牛由变量 Pi.j 表示，其中 i 是奶牛索引，j 是交换迭代。这些变量将各自包含一个与该奶牛的唯一 ID 相对应的整数。此外，为简单起见，我们将只考虑每次迭代的单个反转操作，并在稍后扩展以包括两者。
从 P0.0（第 0 个位置，第 0 次迭代）开始，我们要开始定义一些方程式，以便在下一次迭代中为我们提供给定位置的奶牛。如果母牛在反转区域之外，这是微不足道的；牛没有改变。如果它在反转区域内，我们将要根据反转区域的端点计算新牛的先前位置。明确地：
- 如果在反转区域之外：
Pi.(j+1) = Pi.j
- 其他：
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 向量时，将 return 一个新的奶牛 ID 向量 post-反转.
这就是事情变得有趣的地方。我们可以对另一个反转区域做同样的事情，制作第二个矩阵 MB，并将其与 MA 相乘得到一个整体矩阵 M，它将两个反转合二为一。从这里，我们可以将矩阵提高到 K 次方（迭代次数），对于单个矩阵，它将在所有反转发生后计算每个位置的奶牛。
现在，此时，您可能会质疑这种方法的性能 - 毕竟，我们正在将 100x100 矩阵的某个幂 K 提高到 109！好吧，我们有一些技巧可以使这更快。首先，注意一头奶牛，任何一头奶牛，我们都可以通过对所有反转操作的洗牌进行逻辑推理并确定它的结束位置，所有这些都不知道其他奶牛在哪里/其他奶牛是哪个。
这意味着对于任何给定时间的任何给定位置，该位置的奶牛可以由任何其他迭代中的另一个位置精确定义（例如，P12.7（位置 12 迭代 7）可以通过知道cow 在迭代中的相应位置，比如迭代 5- P8.5).
这很有用，因为这意味着我们矩阵的每一行都将有一个非零元素，并且该元素的值为 1（系数 1 在系统中方程）所以我们实际上可以将我们的 100x100 矩阵压缩成一个只有 100 个值的数组，说明每行的哪一列包含 1.
太好了，我们可以使用这个技巧在 O(n^2) 时间内简单地乘以矩阵。好吧，我们实际上可以做得更好——我们实际上可以在 O(n) 时间内将它们相乘。对于第一个矩阵中的每个“行”R（仅包含列索引，1 值的 I），查看第二个矩阵中的第 I 行，并得到它的值C。将我们在输出矩阵中的相应行 R' 分配为等于 C.
因此我们可以将这些矩阵相乘约 100 个逻辑步骤，但我们需要将此矩阵提高到 K 次方，最多可达 109。我们刚刚从我们的工作中删除了 100 倍，只是为了把它加回来！好吧，不完全是。有一种著名的矩阵求幂方法称为“平方求幂”，我们巧妙地错开重复乘法和求平方的结果，以在 log(K) iterations/steps 中计算 M^K。我不会在这里详细介绍，因为它广为人知且有据可查。
总的来说，这使我们处于 O(N log K) 时间，还不错！
更新：这是解决问题的功能代码。
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]
在使用 timeit 进行了 number=100 次迭代的一些基准测试之后，这些是我的发现（计时以秒为单位，越小越好）：
contributor | time (sec)
------------------------------
blhsing | 7.857691
Michael Szczesny | 5.076418
(mine) | 0.013314
所以 Michael 改进了 blhsing 的解决方案，在我的机器上 运行ning 快了大约 1.5 倍，而我的解决方案 运行 比 Michael 的解决方案快了大约 381 倍，大约花费了十分之一秒平均每个 运行。
更新 2：正如这个答案的评论中提到的，上面的解决方案仍然可以扩展 K，所以最终它会变得棘手，这个问题似乎发出了一种重复的模式——我们当然可以利用它吗？嗯，是的，事实上我们可以。
诀窍在于，在这些奶牛达到我们之前见过的某个先前状态之前，我们只有这么多方法可以排列这些奶牛，然后从那里形成一个无限循环。事实上 - 由于手头问题的简单性，在我们回到之前的状态（实际上是我们的 starting 状态之前，通常只有相对较少的洗牌/反转，因为在不首先访问我们的起始状态的情况下访问任何其他牛排列将意味着有两个不同的状态过渡到所述状态，这不可能是 - 我们的方程组告诉我们否则）。
所以，如果找到奶牛洗牌/反转开始重复的神奇数字，并使用它来将指数（在我们的矩阵求幂中）从 K 减少到 K mod MAGIC.我们实际上将把这个数字称为转移矩阵的乘法阶。首先，请注意可能有不止一个循环的奶牛洗牌，每个奶牛都以句点重复。 4 头奶牛的一个子集可能每 4 次迭代循环一次位置，而另一个 3 头奶牛的子集每 3 次迭代循环一次，这意味着 7 头奶牛每 12 次迭代重复它们的起始配置。
更一般地说，我们需要找到牛洗牌的每个独立周期，得到它们的长度，并找到这些周期的最小公倍数（LCM）。一旦我们有了它，取 K mod 那个，并将我们的矩阵提高到那个 new 值。这样做的示例代码：
from itertools import count
from functools import reduce
from math import lcm
def order(m):
cycle_lens = []
unvisited = set(m)
while unvisited:
start = head = unvisited.pop()
for size in count(1):
head = m[head]
if head == start:
cycle_lens.append(size)
break
unvisited.discard(head)
return reduce(lcm, cycle_lens)
# And inside solve()-
# replace: mk = exp(m0, k)
# with: mk = exp(m0, k % order(m0))
代码性能的主要问题是您使用一个列表来保存每次迭代中奶牛位置的历史记录，以便检测循环，这需要 O(n) 用于使用 in 运算符的每个成员查找。
相反，您可以为此目的使用集合，这会在成员查找中花费 O(1)。但是由于您仍然需要迭代 k % i 次，其中 i 是循环的长度，以到达该特定位置循环，如果集合是有序的会更好，这样你就可以简单地得到集合中的 (k % i) 索引条目，而不必执行那么多次反转。但是由于 set 在 Python 中是无序的，你可以改用字典，其中的键是从 Python 3.6:
开始排序的
from itertools import islice
n, k, a1, a2, b1, b2 = map(int, '''100 1000000000
1 94
2 98'''.split())
cows = list(range(1, n + 1))
history = {}
for i in range(k):
key = tuple(cows)
if key in history:
cows = next(islice(history, k % i, None))
break
history[key] = 1
for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)):
cows[bound] = reversed(cows[bound])
print(*cows, sep='\n')
这输出：
71
2
3
74
10
76
7
8
79
15
81
12
13
84
20
86
17
18
89
25
91
22
23
94
30
96
27
28
1
35
4
32
33
6
40
9
37
38
11
45
14
42
43
16
50
19
47
48
21
55
24
52
53
26
60
29
57
58
31
65
34
62
63
36
70
39
67
68
41
75
44
72
73
46
80
49
77
78
51
85
54
82
83
56
90
59
87
88
61
95
64
92
93
66
5
69
97
98
99
100
你可以摆脱查找。这计算了两次必要的 5680 交换，但为字典保存了额外的 space。在 google colab 实例上，对于此特定示例，此解决方案的运行速度比 快 33%。
n, k, a1, a2, b1, b2 = [int(x) for x in
'''
100 1000000000
1 94
2 98
'''.split()]
a1 -= 1
b1 -= 1
cows = list(range(1, n+1))
rot = cows[:]
s = k
while k:
rot[a1:a2] = reversed(rot[a1:a2])
rot[b1:b2] = reversed(rot[b1:b2])
k -= 1
if rot == cows:
print(f'found frequency {s-k}')
k %= s-k
print(*rot)
输出
found frequency 29640
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
我编写了他的方法并将运行时间提高了 4 倍，达到@dillondavis 的第一个解决方案（320 µs / 78.9 µs）
n, k, a1, a2, b1, b2 = [int(x) for x in
'''
100 1000000000
1 94
2 98
'''.split()]
a1 -= 1
b1 -= 1
cows = list(range(n))
cows[a1:a2] = reversed(cows[a1:a2])
cows[b1:b2] = reversed(cows[b1:b2])
visited = set()
runs = []
for i in cows:
if i not in visited:
run = [i]
nex = cows[i]
while nex != i:
run.append(nex)
nex = cows[nex]
visited.add(nex)
runs.append(run)
for i in runs:
r = k % len(i)
for x,y in zip(i, i[r:]+i[:r]):
cows[x] = y+1
print(*cows)
输出
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
这是一个 O(N) 无论 K 可能是什么都有效的方法。
简明解释：重写循环符号中的排列。使用循环符号生成答案。 （除非我们不需要完整的循环符号。
为了说明，我将使用您的示例，但我将在 999 步后找到排列。
正如您所注意到的，[1,5,7,6,2,3,4] 是 A 然后 B 的一次迭代的结果。以这种形式计算，显然需要 O(N) 的工作。写成这样更方便一些：
{
1: 1,
2: 5,
3: 6,
4: 7,
5: 2,
6: 4,
7: 3
}
同样，此翻译需要 O(N) 工作。
现在让我们计算一个部分答案。我们从 [0,0,0,0,0,0,0]' where 0` 开始，表示“未知”。
第一步，我们找到1 -> 1，所以第一个循环就是(1)。围绕这个循环 999 次再次得到 (1)，所以我们现在有 [1,0,0,0,0,0,0].
第二步，我们发现2 -> 5 -> 2（注意，我们只是在查找中查找这些，所以每个都是O(1)工作）所以第二个循环是(2, 5).绕过这个循环 999 步意味着我们要填写 2 个值。我们现在有 [1,5,0,0,2,0,0].
第三步，我们找到3 -> 6 -> 4 -> 7 -> 3。所以第三个循环就是(3, 6, 4, 7)。绕这 999 圈相当于向前走了 3 步，所以现在我们可以填写：[1,5,7,6,2,3,4].
当我们检查其余的数字时，我们发现它们都已填写。所以我们的答案是 [1,5,7,6,2,3,4]。
一般来说，每个数字都是长度为 j 的循环的一部分。当我们找到一个循环时，我们需要 O(j) 工作来找到循环，然后对于另一个 O(j) 工作，我们填写该循环发生的事情的答案。之后我们将点击 j-1 个已填充的元素并跳过它们。所以我们得到 n 个元素用于 O(n) 个工作，每个元素的分摊 O(1) 个工作。
结果是O(N)努力寻找最终答案。
这是我理解的另一个版本 cycle approach. Working Python code submitted to USACO:
import collections
def f(n, k, ai, aj, bi, bj):
# A cycle necessarily has even parity as both A and B
# must be run. We know a cycle is complete when the
# element returns to the start and the parity is even.
cycles = collections.defaultdict(list)
# Get cycles
for i in range(1, n + 1):
j = i
parity = 0
first_cycle = 1
while first_cycle or j != i or parity:
# A
if not parity:
j = j if (j < ai or j > aj) else aj - j + ai
# B
else:
j = j if (j < bi or j > bj) else bj - j + bi
first_cycle = 0
if parity:
cycles[i].append(j)
parity ^= 1
new_list = [None] * n
for i in range(1, n + 1):
idx = cycles[i][(k - 1) % len(cycles[i])]
new_list[idx-1] = str(i)
file = open("swap.out", "w")
file.write("\n".join(new_list))
file.close()
file = open("swap.in","r")
data = file.readlines()
[n, k] = map(int, data[0].split())
[ai, aj] = map(int, data[1].split())
[bi, bj] = map(int, data[2].split())
f(n, k, ai, aj, bi, bj)
"""
ai = 2
aj = 5
bi = 3
bj = 7
n = 7
k = 2
"""
"""
1
2
4
3
5
7
6
"""
根据我的理解 的另一个实现，在我意识到 @MichaelSzczesny 发布他之前写的：
n, k, a1, a2, b1, b2 = map(int, '''100 1000000000
1 94
2 98'''.split())
*positions, = *mapped, = range(n)
for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)):
mapped[bound] = reversed(mapped[bound])
mapping = dict(zip(mapped, positions))
cycles = []
pool = set(positions)
while pool:
current = pool.pop()
cycle = [current]
while True:
current = mapping[current]
if current == cycle[0]:
break
pool.remove(current)
cycle.append(current)
cycles.append(cycle)
result = [0] * n
for cycle in cycles:
for i, position in enumerate(cycle):
result[cycle[(k + i) % len(cycle)]] = position + 1
print(*result)
这输出：
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
时间统计显示这比@MichaelSzczesny 的实现要快一些：
https://replit.com/@blhsing/EquatorialRemorsefulMath
我正在尝试解决涉及反转列表拼接的问题，但我在测试用例的时间限制方面遇到了问题，该时间限制为 4 秒。问题：
Farmer John的N头奶牛（1≤N≤100）排成一排。从左数第 i 头奶牛的标签为 i，每个 1≤i≤N。 农夫约翰为奶牛制定了新的晨练计划。他让他们重复以下两步过程恰好 K (1≤K≤1000000000) 次：
当前位置A1…A2的奶牛顺序从左倒序（1≤A1 得分：
测试用例2-3满足K≤100。
测试用例 4-13 不满足任何附加约束。 输入格式（文件swap.in）：
输入的第一行是N和K，第二行是A1和A2，第三行是B1和B2。 输出格式（文件swap.out）：
在输出的第 i 行，在 exercise routine 结束时打印左起第 i 头奶牛的标签。 样本输入: 样本输出： 最初，奶牛的顺序是从左到右[1,2,3,4,5,6,7]。在流程的第一步之后，顺序为 [1,5,4,3,2,6,7]。经过第二步流程后，顺序为[1,5,7,6,2,3,4]。再次重复这两个步骤会产生样本的输出。 理论上，您可以通过找到程序重复的点，然后反向模拟 我的程序需要 100 多秒才能完成 运行。这个输入特别耗时，因为它运行是最大迭代次数， 当前代码： 如果有人知道解决这个问题的方法，请post回答。如果有任何不清楚的地方，请发表评论。7 2
2 5
3 7
1
2
4
3
5
7
6
k % frequency次来解决此问题，其中frequency是模拟唯一的次数。
但我的问题是当输入是：100 1000000000
1 94
2 98
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 - 其他：
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 向量时，将 return 一个新的奶牛 ID 向量 post-反转.
这就是事情变得有趣的地方。我们可以对另一个反转区域做同样的事情，制作第二个矩阵 MB，并将其与 MA 相乘得到一个整体矩阵 M，它将两个反转合二为一。从这里，我们可以将矩阵提高到 K 次方（迭代次数），对于单个矩阵，它将在所有反转发生后计算每个位置的奶牛。
现在，此时，您可能会质疑这种方法的性能 - 毕竟，我们正在将 100x100 矩阵的某个幂 K 提高到 109！好吧，我们有一些技巧可以使这更快。首先，注意一头奶牛，任何一头奶牛，我们都可以通过对所有反转操作的洗牌进行逻辑推理并确定它的结束位置，所有这些都不知道其他奶牛在哪里/其他奶牛是哪个。
这意味着对于任何给定时间的任何给定位置，该位置的奶牛可以由任何其他迭代中的另一个位置精确定义（例如，P12.7（位置 12 迭代 7）可以通过知道cow 在迭代中的相应位置，比如迭代 5- P8.5).
这很有用，因为这意味着我们矩阵的每一行都将有一个非零元素，并且该元素的值为 1（系数 1 在系统中方程）所以我们实际上可以将我们的 100x100 矩阵压缩成一个只有 100 个值的数组，说明每行的哪一列包含 1.
太好了，我们可以使用这个技巧在 O(n^2) 时间内简单地乘以矩阵。好吧，我们实际上可以做得更好——我们实际上可以在 O(n) 时间内将它们相乘。对于第一个矩阵中的每个“行”R（仅包含列索引，1 值的 I），查看第二个矩阵中的第 I 行，并得到它的值C。将我们在输出矩阵中的相应行 R' 分配为等于 C.
因此我们可以将这些矩阵相乘约 100 个逻辑步骤，但我们需要将此矩阵提高到 K 次方，最多可达 109。我们刚刚从我们的工作中删除了 100 倍，只是为了把它加回来！好吧，不完全是。有一种著名的矩阵求幂方法称为“平方求幂”，我们巧妙地错开重复乘法和求平方的结果，以在 log(K) iterations/steps 中计算 M^K。我不会在这里详细介绍，因为它广为人知且有据可查。
总的来说，这使我们处于 O(N log K) 时间，还不错！
更新：这是解决问题的功能代码。
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]
在使用 timeit 进行了 number=100 次迭代的一些基准测试之后，这些是我的发现（计时以秒为单位，越小越好）：
contributor | time (sec)
------------------------------
blhsing | 7.857691
Michael Szczesny | 5.076418
(mine) | 0.013314
所以 Michael 改进了 blhsing 的解决方案，在我的机器上 运行ning 快了大约 1.5 倍，而我的解决方案 运行 比 Michael 的解决方案快了大约 381 倍，大约花费了十分之一秒平均每个 运行。
更新 2：正如这个答案的评论中提到的，上面的解决方案仍然可以扩展 K，所以最终它会变得棘手，这个问题似乎发出了一种重复的模式——我们当然可以利用它吗？嗯，是的，事实上我们可以。
诀窍在于，在这些奶牛达到我们之前见过的某个先前状态之前，我们只有这么多方法可以排列这些奶牛，然后从那里形成一个无限循环。事实上 - 由于手头问题的简单性，在我们回到之前的状态（实际上是我们的 starting 状态之前，通常只有相对较少的洗牌/反转，因为在不首先访问我们的起始状态的情况下访问任何其他牛排列将意味着有两个不同的状态过渡到所述状态，这不可能是 - 我们的方程组告诉我们否则）。
所以，如果找到奶牛洗牌/反转开始重复的神奇数字，并使用它来将指数（在我们的矩阵求幂中）从 K 减少到 K mod MAGIC.我们实际上将把这个数字称为转移矩阵的乘法阶。首先，请注意可能有不止一个循环的奶牛洗牌，每个奶牛都以句点重复。 4 头奶牛的一个子集可能每 4 次迭代循环一次位置，而另一个 3 头奶牛的子集每 3 次迭代循环一次，这意味着 7 头奶牛每 12 次迭代重复它们的起始配置。
更一般地说，我们需要找到牛洗牌的每个独立周期，得到它们的长度，并找到这些周期的最小公倍数（LCM）。一旦我们有了它，取 K mod 那个，并将我们的矩阵提高到那个 new 值。这样做的示例代码：
from itertools import count
from functools import reduce
from math import lcm
def order(m):
cycle_lens = []
unvisited = set(m)
while unvisited:
start = head = unvisited.pop()
for size in count(1):
head = m[head]
if head == start:
cycle_lens.append(size)
break
unvisited.discard(head)
return reduce(lcm, cycle_lens)
# And inside solve()-
# replace: mk = exp(m0, k)
# with: mk = exp(m0, k % order(m0))
代码性能的主要问题是您使用一个列表来保存每次迭代中奶牛位置的历史记录，以便检测循环，这需要 O(n) 用于使用 in 运算符的每个成员查找。
相反，您可以为此目的使用集合，这会在成员查找中花费 O(1)。但是由于您仍然需要迭代 k % i 次，其中 i 是循环的长度，以到达该特定位置循环，如果集合是有序的会更好，这样你就可以简单地得到集合中的 (k % i) 索引条目，而不必执行那么多次反转。但是由于 set 在 Python 中是无序的，你可以改用字典，其中的键是从 Python 3.6:
开始排序的from itertools import islice
n, k, a1, a2, b1, b2 = map(int, '''100 1000000000
1 94
2 98'''.split())
cows = list(range(1, n + 1))
history = {}
for i in range(k):
key = tuple(cows)
if key in history:
cows = next(islice(history, k % i, None))
break
history[key] = 1
for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)):
cows[bound] = reversed(cows[bound])
print(*cows, sep='\n')
这输出：
71
2
3
74
10
76
7
8
79
15
81
12
13
84
20
86
17
18
89
25
91
22
23
94
30
96
27
28
1
35
4
32
33
6
40
9
37
38
11
45
14
42
43
16
50
19
47
48
21
55
24
52
53
26
60
29
57
58
31
65
34
62
63
36
70
39
67
68
41
75
44
72
73
46
80
49
77
78
51
85
54
82
83
56
90
59
87
88
61
95
64
92
93
66
5
69
97
98
99
100
你可以摆脱查找。这计算了两次必要的 5680 交换，但为字典保存了额外的 space。在 google colab 实例上，对于此特定示例，此解决方案的运行速度比
n, k, a1, a2, b1, b2 = [int(x) for x in
'''
100 1000000000
1 94
2 98
'''.split()]
a1 -= 1
b1 -= 1
cows = list(range(1, n+1))
rot = cows[:]
s = k
while k:
rot[a1:a2] = reversed(rot[a1:a2])
rot[b1:b2] = reversed(rot[b1:b2])
k -= 1
if rot == cows:
print(f'found frequency {s-k}')
k %= s-k
print(*rot)
输出
found frequency 29640
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
我编写了他的方法并将运行时间提高了 4 倍，达到@dillondavis 的第一个解决方案（320 µs / 78.9 µs）
n, k, a1, a2, b1, b2 = [int(x) for x in
'''
100 1000000000
1 94
2 98
'''.split()]
a1 -= 1
b1 -= 1
cows = list(range(n))
cows[a1:a2] = reversed(cows[a1:a2])
cows[b1:b2] = reversed(cows[b1:b2])
visited = set()
runs = []
for i in cows:
if i not in visited:
run = [i]
nex = cows[i]
while nex != i:
run.append(nex)
nex = cows[nex]
visited.add(nex)
runs.append(run)
for i in runs:
r = k % len(i)
for x,y in zip(i, i[r:]+i[:r]):
cows[x] = y+1
print(*cows)
输出
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
这是一个 O(N) 无论 K 可能是什么都有效的方法。
简明解释：重写循环符号中的排列。使用循环符号生成答案。 （除非我们不需要完整的循环符号。
为了说明，我将使用您的示例，但我将在 999 步后找到排列。
正如您所注意到的，[1,5,7,6,2,3,4] 是 A 然后 B 的一次迭代的结果。以这种形式计算，显然需要 O(N) 的工作。写成这样更方便一些：
{
1: 1,
2: 5,
3: 6,
4: 7,
5: 2,
6: 4,
7: 3
}
同样，此翻译需要 O(N) 工作。
现在让我们计算一个部分答案。我们从 [0,0,0,0,0,0,0]' where 0` 开始，表示“未知”。
第一步，我们找到1 -> 1，所以第一个循环就是(1)。围绕这个循环 999 次再次得到 (1)，所以我们现在有 [1,0,0,0,0,0,0].
第二步，我们发现2 -> 5 -> 2（注意，我们只是在查找中查找这些，所以每个都是O(1)工作）所以第二个循环是(2, 5).绕过这个循环 999 步意味着我们要填写 2 个值。我们现在有 [1,5,0,0,2,0,0].
第三步，我们找到3 -> 6 -> 4 -> 7 -> 3。所以第三个循环就是(3, 6, 4, 7)。绕这 999 圈相当于向前走了 3 步，所以现在我们可以填写：[1,5,7,6,2,3,4].
当我们检查其余的数字时，我们发现它们都已填写。所以我们的答案是 [1,5,7,6,2,3,4]。
一般来说，每个数字都是长度为 j 的循环的一部分。当我们找到一个循环时，我们需要 O(j) 工作来找到循环，然后对于另一个 O(j) 工作，我们填写该循环发生的事情的答案。之后我们将点击 j-1 个已填充的元素并跳过它们。所以我们得到 n 个元素用于 O(n) 个工作，每个元素的分摊 O(1) 个工作。
结果是O(N)努力寻找最终答案。
这是我理解的另一个版本
import collections
def f(n, k, ai, aj, bi, bj):
# A cycle necessarily has even parity as both A and B
# must be run. We know a cycle is complete when the
# element returns to the start and the parity is even.
cycles = collections.defaultdict(list)
# Get cycles
for i in range(1, n + 1):
j = i
parity = 0
first_cycle = 1
while first_cycle or j != i or parity:
# A
if not parity:
j = j if (j < ai or j > aj) else aj - j + ai
# B
else:
j = j if (j < bi or j > bj) else bj - j + bi
first_cycle = 0
if parity:
cycles[i].append(j)
parity ^= 1
new_list = [None] * n
for i in range(1, n + 1):
idx = cycles[i][(k - 1) % len(cycles[i])]
new_list[idx-1] = str(i)
file = open("swap.out", "w")
file.write("\n".join(new_list))
file.close()
file = open("swap.in","r")
data = file.readlines()
[n, k] = map(int, data[0].split())
[ai, aj] = map(int, data[1].split())
[bi, bj] = map(int, data[2].split())
f(n, k, ai, aj, bi, bj)
"""
ai = 2
aj = 5
bi = 3
bj = 7
n = 7
k = 2
"""
"""
1
2
4
3
5
7
6
"""
根据我的理解
n, k, a1, a2, b1, b2 = map(int, '''100 1000000000
1 94
2 98'''.split())
*positions, = *mapped, = range(n)
for bound in map(slice, (a1 - 1, b1 - 1), (a2, b2)):
mapped[bound] = reversed(mapped[bound])
mapping = dict(zip(mapped, positions))
cycles = []
pool = set(positions)
while pool:
current = pool.pop()
cycle = [current]
while True:
current = mapping[current]
if current == cycle[0]:
break
pool.remove(current)
cycle.append(current)
cycles.append(cycle)
result = [0] * n
for cycle in cycles:
for i, position in enumerate(cycle):
result[cycle[(k + i) % len(cycle)]] = position + 1
print(*result)
这输出：
71 2 3 74 10 76 7 8 79 15 81 12 13 84 20 86 17 18 89 25 91 22 23 94 30 96 27 28 1 35 4 32 33 6 40 9 37 38 11 45 14 42 43 16 50 19 47 48 21 55 24 52 53 26 60 29 57 58 31 65 34 62 63 36 70 39 67 68 41 75 44 72 73 46 80 49 77 78 51 85 54 82 83 56 90 59 87 88 61 95 64 92 93 66 5 69 97 98 99 100
时间统计显示这比@MichaelSzczesny 的实现要快一些： https://replit.com/@blhsing/EquatorialRemorsefulMath