Calculating Mahonian Numbers

Problem Inversions

Find the number of permutations of $1, 2, . . ., N$ with exactly $K$ inversions (modulus $2$ ).

Summary of my approach

Step 1

Figure it is called “mahonian triangle numbers”, either by using OEIS or by reading at the bottom of this wikipedia page inversions.

Step 2

Find the relationship with “Truncated Euler Product Triangle” from this paper.

You can basically write mahonian numbers as: $M (r, c) = \sum_{k = 0}^{c} (\binom{r + c - k}{r}) P (r, k)$

Step 3

Realize that if $c < r$ then $P (r, k)$ becomes only a function of $k$ (Every row is a prefix of the next row!). The paper also points out that: $P (r, c) = p (c)$ for $c < r + 2$ .

Step 4

Since we want the answer modulus 2, $(\binom{N}{K}) mod 2$ can be done in $O (1)$ . Read my other post to see how.

Step 5

Finally, if you generate p(c) for c up to 100, you realize that it is very sparse!

1 -1 -1 0 0 1 0 1 0 0 0 0 -1 0 0 -1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ...

Doing some research, it turns out the non-zero indices are a series called Generalized Pentagonal Numbers and there is an efficient way to generate them one by one. Using Pentagonal Number Theorem, you can generate the non-zero indices. The k-th index $G_{k}$ is calculated as: $G_{k} = \frac{k (3 k - 1)}{2}$ for k = 1, −1, 2, −2, 3, -3, …

Code and Time Complexity

There are $\sqrt{N}$ non-zero terms and for each term we do $O (1)$ calculation. So the total time complexity is $O (\sqrt{N})$ .

Here is the code I submitted during the contest and below is a cleaned up version of it.

#include <iostream>

using namespace std;

typedef long long ll;

ll comb2(ll n, ll p) {
    return (p & (n - p)) ? 0 : 1;
}

ll g(ll n) {
    return (3 * n * n - n) / 2;
}

ll calc(ll r, ll c, ll n, ll num) {
    return (2 + comb2(r + c - n, r) * (num % 2 == 0 ? 1 : -1) ) % 2;
}

ll mahonian(ll r, ll c) {
    ll res = calc(r, c, 0, 0);
    for (ll num = 1; ; num++) {
        for (ll mul: {1, -1}) {
            ll nxt = g(num * mul);
            if (nxt >= c + 1) return res;
            res = (res + calc(r, c, nxt, num)) % 2;
        }
    }
}

int main() {
    ll tc, n, k;
    cin >> tc;
    while (tc--) {
        cin >> n >> k;
        cout << mahonian(n-1, k) << endl;
    }
    return 0;
}

Nima Aghdaii