Pythonの最初のn個の自然数の順列から魔法のセットの数を見つけるプログラム

最初のn個の自然数を持つ配列Aと、配列Aの1つの順列P {p1、p2、...pn}があるとします。魔法の集合がいくつあるかを確認する必要があります。これがこれらのいくつかのルールを満たす場合、順列は魔法のセットであると言われます-

• kがある場合、位置a [1]、a [2]、...a[k]の要素は隣接する要素よりも小さくなります[P[a[i]-1]> P [a [i]]

• lがある場合、位置b [1]、b [2]、...b[l]の要素は隣接する要素よりも大きくなります[P[b[i]-1]

  P [b [i] + 1]]

したがって、入力がn =4 k =1 l =1 k_vals =[2] l_vals =[3]の場合、N =4、a [1] =2およびb[1]であるため、出力は5になります。 =3.したがって、5つの順列は[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を入れ替える
  • return 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