数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找前n个自然数排列中的幻方集合数量
假设我们有一个包含前n个自然数的数组A，以及A的一个排列P{p1, p2, ... pn}。我们需要检查有多少个幻方集合。如果排列满足以下规则，则称其为幻方集合：
- 如果我们有k，则位置a[1]、a[2]、... a[k]中的元素小于其相邻元素 [P[a[i] - 1] > P[a[i]] < P[a[i] + 1]]
- 如果我们有l，则位置b[1]、b[2]、... b[l]中的元素大于其相邻元素 [P[b[i] - 1] < P[b[i]] > P[b[i] + 1]]
因此，如果输入为n = 4，k = 1，l = 1，k_vals = [2]，l_vals = [3]，则输出为5，因为：N = 4，a[1] = 2，b[1] = 3。因此，五个排列是[2,1,4,3]、[3,2,4,1]、[4,2,3,1]、[3,1,4,2]、[4,1,3,2]。
为了解决这个问题，我们将遵循以下步骤：
- p := 10^9+7
- F := 一个大小为n+2的数组，并填充为0
- 对于k_vals中的每个a，执行：
- 如果F[a - 1]为1或F[a + 1]为1，则
- 如果F[a - 1]为1或F[a + 1]为1，则
- p := null
- F[a] := 1
- 如果F[a - 1]为1或F[a + 1]为1，则
- 如果F[a - 1]为1或F[a + 1]为1，则
- 对于l_vals中的每个b，执行：
- 如果F[b]为1或F[b - 1]为-1或F[b + 1]为-1，则
- p := null
- F[b] := -1
- 如果F[b]为1或F[b - 1]为-1或F[b + 1]为-1，则
- 如果p等于null，则
- 返回0
- 否则，
- A := 一个大小为n+1的数组，并填充为0
- B := 一个大小为n+1的数组，并填充为0
- FF := 一个大小为n+1的数组，并填充为null
- 对于范围1到n的i，执行：
- FF[i] := F[i] - F[i - 1]
- A[1] := 1
- 对于范围2到n的i，执行：
- 对于范围1到i的j，执行：
- 如果FF[i] > 0，则
- B[j] :=(B[j - 1] + A[j - 1]) mod p
- 否则，如果FF[i] < 0，则
- B[j] :=(B[j - 1] + A[i - 1] - A[j - 1]) mod p
- 否则，
- B[j] :=(B[j - 1] + A[i - 1]) mod p
- 如果FF[i] > 0，则
- 交换A和B
- 对于范围1到i的j，执行：
- 返回A[n]
示例
让我们看下面的实现以更好地理解：
def solve(n, k, l, k_vals, l_vals):
p = 10**9+7
F = [0] * (n + 2)
for a in k_vals:
if F[a - 1] == 1 or F[a + 1] == 1:
p = None
F[a] = 1
for b in l_vals:
if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
p = None
F[b] = -1
if p == None:
return 0
else:
A = [0] * (n + 1)
B = [0] * (n + 1)
FF = [None] * (n + 1)
for i in range(1, n + 1):
FF[i] = F[i] - F[i - 1]
A[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
if FF[i] > 0:
B[j] = (B[j - 1] + A[j - 1]) % p
elif FF[i] < 0:
B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
else:
B[j] = (B[j - 1] + A[i - 1]) % p
A, B = B, A
return A[n]
n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))输入
4, 1, 1, [2], [3]
输入
5
更新于：2021年10月23日
浏览量：93
广告