মনে করুন, দুটি পূর্ণসংখ্যা n এবং k দেওয়া আছে। ১ থেকে n পর্যন্ত সংখ্যা দিয়ে কতগুলো ভিন্ন অ্যারে তৈরি করা যায় যাতে সঠিকভাবে kটি ইনভার্স পেয়ার থাকে। ইনভার্স পেয়ার মানে i < j এবং a[i] > a[j]। উত্তর বড় হতে পারে, তাই 10^9+7 দিয়ে মডুলো নিন।
যেমন, n = 3, k = 1 হলে, আউটপুট ২। অ্যারেগুলো [1,3,2] এবং [2,1,3]।
সমাধানের ধাপসমূহ
- (n+1) x (k+1) আকারের ২D dp অ্যারে সংজ্ঞায়িত করুন
- dp[0][0] := 1
- i := 1 থেকে n পর্যন্ত:
- dp[i][0] := 1
- j := 1 থেকে k পর্যন্ত:
- dp[i][j] := dp[i][j-1] + dp[i-1][j]
- dp[i][j] %= m
- যদি j >= i হয়, dp[i][j] := (dp[i][j] - dp[i-1][j-i] + m) % 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
