পাইথনে পারমিউটেশন থেকে ম্যাজিক সেটের সংখ্যা বের করা

প্রথম n প্রাকৃতিক সংখ্যা অ্যারে A এবং এর একটি পারমিউটেশন P দেওয়া আছে। k পজিশন দেওয়া আছে যেগুলো তাদের আডজেসেন্ট এলিমেন্টের চেয়ে ছোট (ভ্যালি), এবং l পজিশন যেগুলো তাদের আডজেসেন্টের চেয়ে বড় (পিক)। এমন পারমিউটেশন কতটি আছে তা বের করতে হবে। উত্তর ১০⁹+৭ মডুলো।

উদাহরণ

ইনপুট: n = 4, k = 1, l = 1, k_vals = [2], l_vals = [3]

আউটপুট: 5

পারমিউটেশনগুলো: [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4,1,3,2]

সমাধান পদ্ধতি

1. p := 10⁹+7
2. F অ্যারে সাইজ n+2, ০ দিয়ে ফিল।
3. k_vals-এ ১ মার্ক করুন, কনফ্লিক্ট চেক করুন।
4. l_vals-এ -১ মার্ক করুন, কনফ্লিক্ট চেক করুন।
5. কনফ্লিক্ট থাকলে ০ রিটার্ন।
6. ডাইনামিক প্রোগ্রামিং দিয়ে বৈধ পারমিউটেশন কাউন্ট করুন (A, B, FF অ্যারে ব্যবহার করে)।

পাইথন ইমপ্লিমেন্টেশন

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 = [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))  # আউটপুট: 5

ইনপুট

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

আউটপুট

5