Đếm số tập "magic" từ hoán vị n số tự nhiên đầu tiên trong Python

Cho n, k, l, mảng k_vals (vị trí cực tiểu), l_vals (vị trí cực đại). Hoán vị P của 1..n là "magic" nếu:

• Tại các vị trí a[i] (từ k_vals): P[a[i]-1] > P[a[i]] < P[a[i]+1] (cực tiểu).
• Tại các vị trí b[i] (từ l_vals): P[b[i]-1] < P[b[i]] > P[b[i]+1] (cực đại).

Ví dụ: n=4, k=1, l=1, k_vals=[2], l_vals=[3] → 5 hoán vị.

Giải thuật

• Kiểm tra tính nhất quán của điều kiện cực trị (không xung đột).
• Xây dựng mảng FF biểu thị thay đổi kiểu cực trị.
• Quy hoạch động: A[j] = số cách xếp j phần tử đầu tiên thỏa mãn điều kiện.
• Chuyển trạng thái dựa trên FF[i] (>0: cực tiểu, <0: cực đại, =0: tự do).

Ví dụ mã Python

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:
            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]) % 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))  # Output: 5

Đầu vào

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

Đầu ra

5