/* Here's solution that is way too slow -- it uses next_permutation() to generate all of the permutations of the vector of numbers, and then you count up the inverse pairs. */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Solution { public: int kInversePairs(int n, int k); }; int Solution::kInversePairs(int n, int k) { int np, x, i, j; vector v; for (i = 0; i < n; i++) v.push_back(i); np = 0; do { x = 0; for (i = 0; i < n; i++) { for (j = i+1; j < n; j++) { if (v[i] > v[j]) x++; } } if (x == k) np++; } while (next_permutation(v.begin(), v.end())); return np; } int main() { int n, k; Solution s; cin >> n >> k; cout << s.kInversePairs(n, k) << endl; return 0; }