মান লিইয়ে নিই দুটি পূর্ণসংখ্যা n এবং k রয়েছে, আমাদের বের করতে হবে 1 থেকে n পর্যন্ত সংখ্যা দিয়ে কতগুলো ভিন্ন অ্যারে তৈরি করা যায় যাতে ঠিক kটি ইনভার্স পেয়ার থাকে। ইনভার্স পেয়ার বলতে অ্যারেতে i-তম এবং j-তম উপাদানের জন্য, যদি i < j এবং a[i] > a[j] হয়, তবে সেটি একটি ইনভার্স পেয়ার कहলায়। যেহেতু উত্তর খুব বড় হতে পারে, উত্তরটি $10^{9}$ + 7 দিয়ে মডুলো করে দিতে হবে।
সুতরাং যদি ইনপুট হয় n = 3 এবং k = 1, তবে আউটপুট হবে 2 কারণ অ্যারে [1,3,2] এবং [2,1,3]-এ শুধু একটি ইনভার্স পেয়ার রয়েছে।
समाधान पद्धति
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- আকার (n + 1) x (k + 1) এর একটি 2D dp সরণি সংজ্ঞায়িত করুন
- dp[0, 0] := 1
- i := 1 থেকে आरंभ করুন, जब i <= n, আপডেট করুন (i 1 বাড়ান), করুন:
- dp[i, 0] := 1
- j := 1 থেকে आरंभ করুন, जब j <= k, আপডেট করুন (j 1 বাড়ান), করুন:
- dp[i, j] := dp[i, j - 1] + dp[i - 1, j]
- dp[i, j] := dp[i, j] mod m
- যদি j >= i, তবে:
- dp[i, j] := (dp[i, j] - dp[i - 1, j - i] + m) mod m
- dp[n, k] ফেরত দিন
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int m = 1e9 + 7; class Solution { public: int kInversePairs(int n, int k) { vector < vector <int> > dp(n + 1, vector <int>(k + 1)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ dp[i][0] = 1; for(int j = 1; j <= k; j++){ dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; dp[i][j] %= m; if(j >= i){ dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m; } } } return dp[n][k]; } }; main(){ Solution ob; cout << (ob.kInversePairs(4,2)); }
इनपुट
4 2
आउटपुट
5
