/* * Runtime: 235 ms, faster than 12.18% of C++ online submissions for K Inverse Pairs Array. * Memory Usage: 16.8 MB, less than 21.15% of C++ online submissions for K Inverse Pairs Array. * * See the writeup for how this solution works. */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Solution { public: int kInversePairs(int n, int k); vector < vector > Cache; }; long long BP = 1000000007; int Solution::kInversePairs(int n, int k) { long long i; long long sum; long long r1, r2, r3; if (k == 0) return 1; if (n == 0) return 0; if (Cache.size() == 0) { Cache.resize(n+1); for (i = 0; i < Cache.size(); i++) Cache[i].resize(k+1, -1); } if (Cache[n][k] != -1) return Cache[n][k]; r1 = kInversePairs(n,k-1); r2 = kInversePairs(n-1,k); r3 = 0; if (k >= n) r3 = kInversePairs(n-1,k-n); sum = r1 + r2 - r3; if (sum < 0) sum += BP; // If r3 is bigger than r1 and r2, then you need to do this. sum %= BP; Cache[n][k] = sum; return sum; } int main() { int n, k; Solution s; cin >> n >> k; cout << s.kInversePairs(n, k) << endl; return 0; }