C++のK逆ペア配列

2つの整数nとkがあるとすると、正確にk個の逆数のペアが存在するように、1からnまでの数で構成される異なる配列の数を見つける必要があります。逆ペアは、配列のi番目とj番目の要素用であり、i a [j]の場合、逆ペアと呼ばれます。ここで、答えは非常に大きくなる可能性があります。答えは$ 10 ^ {9} $+7を法とする必要があります。

したがって、入力がn=3およびk=1の場合、配列[1,3,2]および[2,1,3]には1つの逆ペアしかないため、出力は2になります。

これを解決するには、次の手順に従います-

• サイズ（n + 1）x（k + 1）の2D配列dpを1つ定義します
• 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
• return 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