C++의 K 역쌍 배열

<시간/>

두 개의 정수 n과 k가 있다고 가정하고 정확히 k개의 역쌍이 있도록 1에서 n까지의 숫자로 구성된 다른 배열의 수를 찾아야 합니다. 역쌍은 배열의 i번째 및 j번째 요소에 대한 것이며, i a[j]이면 역쌍이라고 합니다. 여기에서 답은 매우 클 수 있습니다. 답은 모듈로 $10^{9}$ + 7이어야 합니다.

따라서 입력이 n =3 및 k =1과 같으면 배열 [1,3,2] 및 [2,1,3]에 역쌍이 하나만 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

(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] 모드 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