数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找经过最多k次相邻交换后的序列数量
假设我们有一个数组A，包含前n个自然数。我们需要找到经过精确k次相邻交换后可以得到多少个序列(S1)？以及经过最多k次交换后可以得到多少个序列(S2)？这里相邻交换是指交换索引i和i+1处的元素。
例如，如果输入n = 3，k = 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]，[1, 3, 2]，[3, 2, 1]
- 2次交换：[1, 2, 3]，[2, 3, 1]，[3, 1, 2]
所以S2 = 6
为了解决这个问题，我们将遵循以下步骤：
- p = 10^9+7
- A := 一个只包含一个元素1的数组
- C := 一个只包含一个元素1的数组
- 对于n从2到n+1，执行：
- B := A，A := 一个只包含一个元素1的数组
- D := C，C := 一个只包含一个元素1的数组
- 对于x从1到min(k+1, 1+2+...+n)
- 将((A的最后一个元素 + (如果x < B的大小，则为B[x]，否则为0) - (如果0 <= x-n，则为B[x-n]，否则为0)) mod p)插入到A的末尾
- 对于x从1到n-2，执行：
- 将((D[x] + (n-1)*D[x-1]) mod p)插入到C的末尾
- 将(n * C的最后一个元素) mod p插入到C的末尾
- 返回(A[从索引k mod 2到k的元素之和] mod p)和C[min(n-1, k)]
示例
让我们来看下面的实现来更好地理解：
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
更新于：2021年10月23日
浏览量：190
广告