• Iterating all possible nth permutation and count the number of inversion pairs (such pair $$$(a[i], a[j])$$$ that $$$a[i] > a[j]$$$ and $$$i < j$$$)

• Count the number of permutations whose number of inversion pairs is $$$k$$$

int n, k;
int inversion_count(const vector<int> &perm) /// count number of inversion in permutation
{
    int res = 0;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (perm[i] < perm[j])
                res++;

    return res;
}

int main()
{
    cin >> n >> k;

    vector<int> perm(n + 1);
    for (int i = 1; i <= n; ++i) /// assigning permutation
        perm[i] = i;   

    int res = 0;
    do {
        if (inversion_count(perm) == k) /// this permutation is valid (having exactly k inversion pairs)
            res++;

    } while (next_permutation(1 + all(perm))); /// iterating all possible permutation
    cout << res;
}

• Using BIT to calculate the number of inversions in $$$O(n log n)$$$

• Using Binary-search to find the last position $$$p$$$ that the amount of inversion pair in $$$[1..p]$$$ of this permutation is the same of next permutation

• Using Dynamic-programming to ignore the part that has been calculated and recalculating different path

vector<int> BIT;
void inc(int p) { /// increase the amount of visited
    do BIT[p]++;
    while (p -= p & -p);
}

void dec(int p) { /// decrease the amount of visited
    do BIT[p]--;
    while (p -= p & -p);
}

int getValue(int p) { /// count number of inversion pairs
    int res = 0;
    do res += BIT[p];
    while ((p += p & -p) < BIT.size());
    return res;
}

int main() 
{
    int n, m;
    cin >> n >> m;

    BIT.assign(n + 1, 0);
    vector<int> perm(n + 1, 0);
    vector<int> calc(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        perm[i] = i; /// assigning value
        calc[i] = calc[i - 1] + getValue(perm[i]); /// dp-precalculating
        inc(perm[i]); /// update value
    }

    int res = 0;
    res += (calc[n] == m);
    /// Iterating over all possible permutation
    for (vector<int> n_perm(perm); next_permutation(1 + all(n_perm)); next_permutation(1 + all(perm)))
    {
        int p = 1; /// position of first different between two consecutive permutations (perm, n_perm)
        for (int l = 1, r = n; l <= r; )
        {
            int m = (l + r) / 2; /// middle point
            if (perm[m] == n_perm[m] && perm[m - 1] == n_perm[m - 1]) /// this position is valid
            {
                p = m;
                l = m + 1;
            }
            else r = m - 1;
        }
        for (int i = p; i <= n; ++i) dec(perm[i]); /// reset the tree before update this path [p..n]
        for (int i = p; i <= n; ++i)
        {
            calc[i] = calc[i - 1] + getValue(n_perm[i]); /// re-calculating the different path
            inc(n_perm[i]); /// update new value
        }
        res += (calc[n] == m); /// increase the counter when it is valid
    }

    cout << res;
    return 0;
}

• The formula is coefficients in expansion of $$$\underset{i \in [0, n)}{\prod}(1+x+...+x^i)$$$

• Lets $$$f[n][k]$$$ be the number of $$$nth$$$ permutation with $$$k$$$ inversion pairs

We have $$$f[n][0] = 1$$$ (since there is only one permutation $$$[1..n]$$$ have $$$0$$$ inversion pairs)

We have $$$f[0][k] = 0$$$ (since there is no elements so there is no inversion pairs)

Becareful with $$$f[0][0] = 1$$$ (since there is no elements there is exactly zero amount of inversion pairs)

Maximum Possible Valid $$$max_k$$$ is $$$\frac{n \times (n + 1)}{2} - 1$$$ (strictly decreasing permutation $$$[n..1]$$$)

Minumum Possible Valid $$$min_k$$$ is $$$0$$$ (strictly increasing permutation $$$[1..n]$$$)

If $$$k$$$ is out of range $$$(k < min_k) or (k > max_k)$$$ then $$$f[n][k] = 0$$$

The total number of possible valid $$$k \in [min_k, max_k]$$$ is $$$total = max_k - min_k + 1 = \frac{n \times (n + 1)}{2}$$$

We have $$$f[n][k] = f[n][total - k]$$$ (since the number of $$$nth$$$ permutations within $$$k$$$ inversion pairs is the same as the number of $$$nth$$$ permutations without $$$k$$$ inversion pairs)

From sequences of permutations $$$f[n]$$$ with all possible $$$k$$$ we can find the sequence $$$f[n + 1]$$$ (you can read here)

We have the formula $$$f[n][k] = sum(f[n - 1][k - 1 \rightarrow k - n])$$$

• Lets $$$f[n][k]$$$ be the number of $$$nth$$$ permutation with no more than $$$k$$$ inversion pairs

By this way, we can calculate $$$f[n][k]$$$ in $$$O(1)$$$ from $$$f[n][k - 1]$$$ and $$$f[n - 1][0..k]$$$

• We can ignore sequences of permutations $$$f[n - 2] \rightarrow f[0]$$$ when it is calculate

By this way, we can calculate $$$f[n][k]$$$ in $$$O(k)$$$ space

vector<vector<int> > f;
int solve(int n, int k)
{
    int total = n * (n - 1) / 2;       /// number of possible k
    if (k < 0 || k > total) return 0;  /// k is out of range
    minimize(k, total - k);            /// f[n][k] = f[n][total - k]
    if (f[n][k] != -1) return f[n][k]; /// if f[n][k] is calculated
    if (k == 0) return f[n][0] = 1;    /// strictly increasing permutation
    if (n == 0) return f[0][k] = 0;    /// empty permutation
    return f[n][k] = (solve(n, k - 1) + solve(n - 1, k) - solve(n - 1, k - n) + MOD) % MOD;
}

int main()
{
    int n, k;
    cin >> n >> k;

    int total = n * (n - 1) / 2;
    if (k < 0 || k > total) /// k is out of range
    {
        cout << 0;
        return 0;
    }

    minimize(k, total - k);  /// f[n][k] = f[n][total - k]
    f.assign(n + 1, vector<int>(k + 1, -1)); /// init dp-table
    cout << solve(n, k);
    return 0;
}

int main()
{
    int n, k;
    cin >> n >> k;

    int total = n * (n - 1) / 2;
    if (k < 0 || k > total) /// k is out of range
    {
        cout << 0;
        return 0;
    }

    minimize(k, total - k);
    int f[n + 1][k + 1];
    f[0][0] = 1; /// base case f[n][0] = 1
    for (int i = 1; i <= n; ++i) f[0][i] = 0; /// base case f[0][k] = 0
    for (int i = 1; i <= n; ++i)
    {
        bool cur = i & 1; /// current
        bool pre = !cur;  /// previous

        f[cur][0] = 1; /// base case f[n][0] = 1
        for (int j = 1; j <= k; ++j)
        {
            f[cur][j] = (f[cur][j - 1] + f[pre][j]) % MOD;
            if (j >= i)
                f[cur][j] = (f[cur][j] - f[pre][j - i] + MOD) % MOD;
        }
    }

    cout << f[n & 1][k];
    return 0;
}