โปรแกรมหาจำนวนชุดเวทย์มนตร์จากการเรียงสับเปลี่ยนของ n ตัวเลขธรรมชาติตัวแรกใน Python

สมมติว่าเรามีอาร์เรย์ A ที่มีจำนวนธรรมชาติ n ตัวแรก และการเปลี่ยนแปลงหนึ่งชุด P{p1, p2, ... pn} ของอาร์เรย์ A เราต้องตรวจสอบว่ามีชุดเวทมนตร์กี่ชุด การเรียงสับเปลี่ยนกล่าวกันว่าเป็นเซตเวทมนตร์ หากเป็นไปตามกฎสองสามข้อนี้ -

ถ้าเรามี 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] ผลลัพธ์จะเป็น 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
สำหรับแต่ละ a ใน k_vals ทำ
- ถ้า F[a - 1] เป็น 1 หรือ F[a + 1] เป็น 1 แล้ว
  - ถ้า F[a - 1] เป็น 1 หรือ F[a + 1] เป็น 1 แล้ว
    - p :=null
  - F[a] :=1
สำหรับแต่ละ b ใน l_vals ทำ
- ถ้า 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 และเติมค่าว่าง
- สำหรับฉันในช่วง 1 ถึง n ทำ
  - FF[i] :=F[i] - F[i - 1]
- A[1] :=1
- สำหรับฉันในช่วง 2 ถึง n ทำ
  - สำหรับ j ในช่วง 1 ถึง i ทำ
    - ถ้า 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]