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
  • 對於l_vals中的每個b，執行：
    • 如果F[b]為1或F[b - 1]為-1或F[b + 1]為-1，則
      • p := null
    • F[b] := -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
      • 交換A和B
    • 返回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

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告