পাইথনে অ্যারেতে k অ্যাডজেসেন্ট সোয়্যাপ ও সর্বোচ্চ k সোয়্যাপের পর সিকোয়েন্সের সংখ্যা

প্রথম n প্রাকৃতিক সংখ্যা অ্যারে A দেওয়া আছে। নিচের দুটি প্রশ্নের উত্তর দিন:

1. S1: ঠিক kটি অ্যাডজেসেন্ট সোয়্যাপ (i এবং i+1 সোয়্যাপ) করার পর কতটি সিকোয়েন্স পাওয়া যায়?
2. S2: সর্বোচ্চ kটি সোয়্যাপ (যেকোনো দুটি এলিমেন্ট সোয়্যাপ) করার পর কতটি সিকোয়েন্স পাওয়া যায়?

উদাহরণ

ইনপুট: n = 3, k = 2

আউটপুট: 3, 6

মূল অ্যারে: [1,2,3]

• ২ অ্যাডজেসেন্ট সোয়্যাপ: [1,2,3], [2,3,1], [3,1,2] → S1 = 3
• সর্বোচ্চ ২ সোয়্যাপ: ০ সোয়্যাপ: [1,2,3]; ১ সোয়্যাপ: [2,1,3],[3,2,1],[1,3,2]; ২ সোয়্যাপ: [1,2,3],[2,3,1],[3,1,2] → S2 = 6

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

1. p = 10⁹+7
2. A := [1], C := [1]
3. n = 2 থেকে n+1 পর্যন্ত লুপ:
   • B := A; A := [1]; D := C; C := [1]
   • x = 1 থেকে min(k+1, n*(n-1)//2 + 1) পর্যন্ত:
     • A.append((A[-1] + (B[x] if x
   • x = 1 থেকে n-2 পর্যন্ত:
     • C.append((D[x] + (n-1)*D[x-1]) % p)
   • C.append(n * D[-1] % p)
4. রিটার্ন sum(A[k%2:k+1:2]) % p এবং C[min(n-1, k)]

p = 10**9 + 7

def solve(n, k):
    A = [1]
    C = [1]
    for n_val in range(2, n + 1):
        B = A
        A = [1]
        D = C
        C = [1]
        for x in range(1, min(k + 1, n_val * (n_val - 1) // 2 + 1)):
            A.append((A[-1] + (B[x] if x < len(B) else 0) - (B[x - n_val] if 0 <= x - n_val else 0)) % p)
        for x in range(1, n_val - 1):
            C.append((D[x] + (n_val - 1) * D[x - 1]) % p)
        C.append(n_val * D[-1] % p)
    return sum(A[k % 2:k + 1:2]) % p, C[min(n - 1, k)]

# টেস্ট
n = 3
k = 2
print(solve(n, k))  # আউটপুট: (3, 6)

3, 2

3, 6