在 Python 中查找相邻 k 次交换和至多 k 次交换后的序列数的程序
假设我们有一个包含前n个自然数的数组A。我们必须找出在A上精确的k个相邻交换后我们可以得到多少个序列(S1)？在A上最多k次交换后，我们可以得到多少个序列(S2)？这里相邻的交换意味着交换索引i和i+1处的元素。
所以，如果输入像n=3k=2，那么输出将是3,6因为-
原始数组是[1,2,3]
经过2次相邻交换后：我们可以得到[1,2,3],[2,3,1],[3,1,2]所以S1=3
最多2次交换后：
0交换后：[1,2,3]
1次交换后：[2,1,3],[3,2,1],[1,3,2]。
2次交换后：[1,2,3],[2,3,1],[3,1,2]
所以S2=6
示例
让我们看看以下实现以获得更好的理解-
p = 10**9+7
def solve(n, k):
A = [1]
C = [1]
for n in range(2,n+1):
B = A
A = [1]
D = C
C = [1]
for x in range(1,min(k+1,n*(n-1)//2+1)):
A.append((A[-1] + (B[x] if x<len(B) else 0) - (B[x-n] if 0<=x-n else 0)) % p )
for x in range(1,n-1):
C.append((D[x]+(n-1)*D[x-1]) % p)
C.append(n*D[-1] % p)
return sum(A[k%2:k+1:2]) % p,C[min(n-1,k)]
n = 3
k = 2
print(solve(n, k))输入
3, 2输出结果
3, 6