পাইথনে অপারেশন করার পর সাবঅ্যারের এক্সপেক্টেড সম বের করার প্রোগ্রাম

প্রদত্ত অ্যারে A যার সাইজ n এবং দুটি ভ্যালু p এবং q। আমরা A-তে নিচের অপারেশনগুলো পারফর্ম করতে পারি:

র‍্যান্ডমলি দুটি ইন্ডেক্স (l, r) সিলেক্ট করুন যেখানে l < r, তারপর A[l] এবং A[r] এক্সচেঞ্জ করুন
র‍্যান্ডমলি দুটি ইন্ডেক্স (l, r) সিলেক্ট করুন যেখানে l < r, তারপর A-র সাবঅ্যারে l থেকে r রিভার্স করুন

প্রথম অপারেশন p বার এবং দ্বিতীয় অপারেশন q বার করার পর, আমরা র‍্যান্ডমলি দুটি ইন্ডেক্স l, r সিলেক্ট করব যেখানে l < r এবং S = sum of A[l..r] ক্যালকুলেট করব, তারপর S-এর এক্সপেক্টেড ভ্যালু বের করব।

উদাহরণস্বরূপ, যদি ইনপুট A = [1,2,3], p = 1, q = 1 হয়, তবে আউটপুট হবে 4.667।

সমাধানের ধাপসমূহ

matmul() ফাংশন ডিফাইন করুন যা a, v, n নেবে
ম্যাট্রিক্স মাল্টিপ্লিকেশন লজিক ব্যবহার করে ট্রান্সফরমেশন ম্যাট্রিক্স প্রয়োগ করুন
সওয়্যাপ এবং রিভার্স অপারেশনকে ম্যাট্রিক্স হিসেবে মডেল করুন
ফাইনাল অ্যারে পাওয়ার পর ডট প্রোডাক্ট ক্যালকুলেট করে এক্সপেক্টেড ভ্যালু বের করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝার জন্য:

def matmul(a, v, n):
    toret = [0]*n
    for i in range(n):
        for j in range(n):
            toret[i] += a[i][j]*v[j]
    return toret

def solve(A, p, q):
    n = len(A)
    temp = []
    swp = (n - 3)/(n - 1)
    swapvalp = (pow(swp, p)*(n - 1) + 1)/n
    swapvalm = (1 - pow(swp, p))/n
    rev = []
    dotv = []
    for i in range(n):
        swaprow = []
        revrow = []
        for j in range(n):
            swaprow.append(swapvalm)
            revrow.append(2*(min(i, j, n - i - 1, n - j - 1) + 1)/(n*(n - 1)))
        swaprow[i] = swapvalp
        revrow[i] = 1.0 - 2*((i + 1)*(n - i) - min(i + 1, n - i))/(n*(n - 1))
        temp.append(swaprow)
        rev.append(revrow)
        dotv.append(2*((i + 1)*(n - i) - 1)/(n*(n - 1)))
    A = matmul(temp, A, n)
    for _ in range(q):
        A = matmul(rev, A, n)
    tot = 0.0
    for i in range(n):
        tot += dotv[i]*A[i]
    return tot

A = [1,2,3]
p = 1
q = 1
print(solve(A, p, q))

ইনপুট

[1,2,3], 1, 1

আউটপুট

4.666666666666667