পাইথনে ইনভার্টেড ইনভার্শন সংখ্যা নির্ণয়

একটি সংখ্যার তালিকা nums দেওয়া আছে যা 1...N এর পারমুটেশন। a nums[d] সিদ্ধ করে এমন চতুর্পদ (a,b,c,d) এর সংখ্যা বের করতে হবে।

উদাহরণ: nums = [3, 4, 7, 6, 5] হলে আউটপুট ৫।

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

মডুলো M := 10^9+7
যদি len(nums) < 4 হয় তবে 0 ফেরত দিন
ডান পাশ থেকে সর্টেড তালিকা রেখে ds_smaller_than_c массив তৈরি করুন
বাম পাশ থেকে সর্টেড তালিকা রেখে as_smaller_than_b_sum গণনা করুন
চতুর্পদ সংখ্যা = as_smaller_than_b_sum * ds_smaller_than_c[b+1] যোগ করুন
ফলাফল মডুলো M দিয়ে ফেরত দিন

উদাহরণ কোড

import bisect
MOD = 10 ** 9 + 7
class Solution:
    def solve(self, nums):
        if len(nums) < 4:
            return 0
        n = len(nums)
        sorted_ds = [nums[-1]]
        sorted_ds.sort()
        ds_smaller_than_c = [0] * n
        for c in range(n - 2, -1, -1):
            ds_smaller_than_c[c] = bisect.bisect_right(sorted_ds, nums[c] - 1)
            sorted_ds.append(nums[c])
            sorted_ds.sort()
        quadruplet_count = 0
        sorted_as = [nums[0]]
        sorted_as.sort()
        as_smaller_than_b_sum = 0
        for b in range(1, n - 2):
            as_smaller_than_b_sum += bisect.bisect_right(sorted_as, nums[b] - 1)
            sorted_as.sort()
            as_smaller_than_b_sum %= MOD
            sorted_as.append(nums[b])
            sorted_as.sort()
            quadruplet_count += as_smaller_than_b_sum * ds_smaller_than_c[b + 1]
            quadruplet_count %= MOD
        return quadruplet_count

ob = Solution()
print(ob.solve([3, 4, 7, 6, 5]))

ইনপুট

[3, 4, 7, 6, 5]