fork download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <vector>
  4.  
  5. class Solution
  6. {
  7.     std::vector<std::vector<int>> memo;
  8.     int M = 1000000007;
  9.  
  10.     int inv(int n, int k)
  11.     {
  12.         if (n == 0)
  13.             return 0;
  14.  
  15.         if (k == 0)
  16.             return 1;
  17.  
  18.         if (memo[n][k] != -1)
  19.             return memo[n][k];
  20.  
  21.         int val = (inv(n - 1, k) + M - ((k - n) >= 0 ? inv(n - 1, k - n) : 0)) % M;
  22.         memo[n][k] = (inv(n, k - 1) + val) % M;
  23.         return memo[n][k];
  24.     }
  25.  
  26. public:
  27.     Solution(int nmax, int kmax)
  28.         : memo(nmax, std::vector<int>(kmax,-1))
  29.     {
  30.     }
  31.  
  32.     int kInversePairs(int n, int k)
  33.     {
  34.         return ((inv(n, k) + M - (k > 0 ? inv(n, k - 1) : 0)) % M);
  35.     }
  36. };
  37.  
  38.  
  39. int main()
  40. {
  41.     Solution sol(1001, 1001);
  42.     std::cout << sol.kInversePairs(1000, 999) << '\n';
  43. }
  44.  
Success #stdin #stdout 0.02s 19232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
40778721
https://ideone.com/xOtZtH
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!