โปรแกรมนับ magic sets จากการเรียงสลับของ n ตัวเลขแรกใน Python

มีอาร์เรย์ A = [1..n] และการเรียงสลับ P ต้องการนับ magic sets ที่สอดคล้องกับเงื่อนไข: ตำแหน่งใน k_vals ต้องเป็น local minima (น้อยกว่าตัวข้างเคียง) และตำแหน่งใน l_vals ต้องเป็น local maxima (มากกว่าตัวข้างเคียง)

ตัวอย่าง: n=4, k=1, l=1, k_vals=[2], l_vals=[3] → ผลลัพธ์ 5

ขั้นตอนการแก้ปัญหา

ใช้ Dynamic Programming บนลำดับความยาว n พร้อมเงื่อนไข local min/max:

1. ตรวจสอบความขัดแย้งของเงื่อนไข (ตำแหน่งซ้อนทับกัน)
2. สร้างอาร์เรย์ FF บ่งชี้ trend (ขึ้น/ลง/คงที่)
3. DP: A[i][j] = จำนวนวิธีสำหรับ prefix ยาว i ที่ลงท้ายด้วยค่าที่เป็นอันดับ j
4. คืนค่า A[n] modulo 10^9+7

ตัวอย่างโค้ด Python

def solve(n, k, l, k_vals, l_vals):
    MOD = 10**9 + 7
    F = [0] * (n + 2)
    for a in k_vals:
        if F[a - 1] == 1 or F[a + 1] == 1:
            return 0
        F[a] = 1
    for b in l_vals:
        if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
            return 0
        F[b] = -1
    A = [0] * (n + 1)
    B = [0] * (n + 1)
    FF = [0] * (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]) % MOD
            elif FF[i] < 0:
                B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % MOD
            else:
                B[j] = (B[j - 1] + A[i - 1]) % MOD
        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))  # ผลลัพธ์: 5

อินพุตตัวอย่าง

4, 1, 1, [2], [3]

เอาต์พุตตัวอย่าง

5