INVSMOD2 - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author : Ildar Gainullin
Tester : Radoslav Dimitrov
Editorialist : Srikkanth

DIFFICULTY:

Medium

PREREQUISITES:

Generating functions, Pentagonal number theorem

PROBLEM:

Find the number of permutations of 1, 2, ... n that have exactly k inversions, modulo 2

QUICK EXPLANATION:

There is a closed form expression for the answer which is given by

f(n, k) = {{n-k-1}\choose{k}} + \sum_{j = 1}^{ \infty } (-1)^j {{n - k - 1 - u_j - j} \choose {k - u_j - j}} + \sum_{j = 1}^{ \infty } (-1)^j {{n - k - 1 - u_j} \choose {k - u_j}}

{n \choose r} \mod 2 is 1 if n \ \& \ k = k and 0 otherwise.

There are only \mathcal{O}(\sqrt {n}) terms in the above expression that are positive in the above formula and each can be evaluated in \mathcal{O}(1).

EXPLANATION:

Finding recurrence relation

Let f(n, k) be the number of permutations of 1, 2, ... n with exactly k inversions.

We can obtain a recursive formula for f, by considering what the first element of the permutation

Suppose we have a permutation of size n, that has k inversions, and the first element is x.

Then there will definitely be atleast x-1 inversions, because numbers 1, 2, ... x-1 will occur after x.

Now the other k-(x-1) inversion will be among the last n-1 elements.

Can we consider the last n-1 elements as a permutaion of size n-1?

As long as the numbers are different, their exact values doesn’t matter. For eg. the set of inversions of {5, 3, 1} is exactly the same as {3, 2, 1}

This is because we can replace every number by it’s position in the sorted array and obtain an identical inversion set.

So we’ve reduced the problem from size n, k to a problem of size n-1, k - (x-1).

Now we can formulate the recurrence by iterating through x.

f(n, k) = \sum_{x=1}^{n} f(n-1, k-x+1)

Base case f(1, k) is 1 if k = 0 and 0 otherwise.

This can be easily implemented with dynamic programming and complexity \mathcal{O}(nk), which is sufficient for subtasks

Generating function

Generating functions are useful to derive some important results in combinatorics. Such as the one here.

From the recurrence relation, we can obtain an explicit formula for f(n, k) using generating functions.
This is a common technique in combinatorics.

For a sequence a, the generating function is a polynomial defined as GF(x) = \sum_{k=0}^{\infty} a_k x^k

Let’s consider the sequence f(n, 0), f(n, 1), ... , and the corresponding generating function F_n

F_n = \sum_{k=0}^{\infty} f(n, k) x^k

Let’s revisit the recurrence relation

f(n, k) = \sum_{t=0}^{n-1} f(n-1, k-t) (replacing x with t-1 here to avoid confusion with the variable x)

\implies f(n, k) x^k = \sum_{t=0}^{n-1} f(n-1, k-t) x^k

\implies f(n, k) x^k = \sum_{t=0}^{n-1} (f(n-1, k-t) x^{k-t}) x^t

Let’s do summation on both sides, from k = 0 to \infty

\implies \sum_{k=0}^{\infty} f(n, k) x^k = \sum_{k=0}^{\infty} \sum_{t=0}^{n-1} (f(n-1, k-t) x^{k-t}) x^t

Rearranging the summation of the right hand side,

\implies \sum_{k=0}^{\infty} f(n, k) x^k = \sum_{t=0}^{n-1} ( \sum_{k=0}^{\infty} (f(n-1, k-t) x^{k-t}) ) x^t

The term on lhs is clearly F_n. Let’s have a closer look at the term inside the second \sum.

We have \sum_{k=0}^{\infty} (f(n-1, k-t) x^{k-t} .

Replacing k' = k - t, we have, \sum_{k'=-t}^{\infty} (f(n-1, k') x^{k'}.

SInce t is always non-negative, the terms having k'= -t to k' = -1 are going to be zero (f(n, -ve) is always 0, so we can drop those terms are write \sum_{k'=0}^{\infty} (f(n-1, k') x^{k'} instead, which is exactly F_{n-1}!.

Therefore, F_n = F_{n-1} \sum_{t=0}^{n-1} x^t

This is a simple recurrence that we can expand (using base case F_1 = 1).

F_n = (1)(1 + x) (1 + x + x^2) ... (1 + x + x^2 + ... x^{n-1})

Using geometric progression formula, we get,

F_n = \{(1-x)(1-x^2)(1-x^3) ... (1-x^n)\} (1-x)^{-n}

Deriving the expression

Let’s try to find the coefficient of x^k in the generating function,

F_n = \{(1-x)(1-x^2)(1-x^3) ... (1-x^n)\} (1-x)^{-n}

The second term, is well known to be \sum_{t=0}^{\infty} {{n+t-1}\choose{t}} (-1)^t x^t

All we want is the coefficient of x^k in F_n.

We can make use of Euler’s pentagonal number theorem to simplify this.

(1-x) (1-x^2) ... (upto \ \infty) = 1 + \sum_{s=1}^{\infty} (-1)^s (x^{\frac{3s(s+1)}{2}} + x^{\frac{3s(s-1)}{2}})

Although there are only n terms in the first (and not \infty like in the formula above), appending additional terms in the expansion doesn’t affect coefficient of x^k ( since k \leq n ).

f(n, k) is equivalent to coefficient of x^k in the expansion

\{(1-x)(1-x^2)(1-x^3) ... (1-x^n) ... upto \ \infty \} (1-x)^{-n}, which is the same as

\{1 + \sum_{s=0}^{\infty} (-1)^s (x^{\frac{3s(s+1)}{2}} + x^{\frac{3s(s-1)}{2}}) \} \sum_{t=0}^{\infty} {{n+t-1}\choose{t}} x^t

There are only a few exponents in the first term which are less than n, for each exponent u in the first term, we can multiply k-u in the second term.

This gives the following formula for f(n, k)

f(n, k) = {{n-k-1}\choose{k}} + \sum_{j = 1}^{ \infty } (-1)^j {{n - k - 1 - u_j - j} \choose {k - u_j - j}} + \sum_{j = 1}^{ \infty } (-1)^j {{n - k - 1 - u_j} \choose {k - u_j}}

ncr modulo 2

We can easily find the exponent of 2 in n!, r!, (n-r)!.
Using this we can find exponent of 2 in n \choose r in \mathcal{O}(\log n)

We can obtain a faster algorithm using Lucas Theorem, which is

{n \choose r} \mod p = {{n_0} \choose {r_0}} {{n_1} \choose {r_1}} ... \ upto \ \infty \mod p where p is prime.

where n_0, n_1, ... are digits of n in base p and r_0, r_1, ... are digits of r in base p.

Substituting for p = 2, each digit is either 0 or 1.

Also, {0 \choose 0} = {1 \choose 0} = {1 \choose 1} = 1 and {0 \choose 1} = 0

If rhs in lucas theorem is 1 then every term must be 1, which means whenever k has a set bit, the corresponding bit in n is set.

This can be checked for all digits with bitwise operators directly, both the following are equivalent n \ \& \ k == k and n \ | \ k == n and are equal to {{n}\choose{r}} \mod 2

TIME COMPLEXITY:

TIME: \mathcal{O}(\sqrt{n})
SPACE: \mathcal{O}(1)

SOLUTIONS:

Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

ll comb(ll n, ll k) {
  if (n < k || k < 0) return 0;
  return ((n & k) == k);
}

ll ans(ll n, ll k) {
  ll ret = comb(n + k - 1, k);
  for (int i = 1; ; i++) {
    ll u = i * (ll) (3 * i - 1) / 2;
    if (u > n) {
      break;
    }
    ret ^= comb(n + k - u - i - 1, k - u - i);
    ret ^= comb(n + k - u - 1, k - u);
  }
  return ret;
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    ll n, k;
    cin >> n >> k;
    cout << ans(n, k) << '\n';
  }
}

3 Likes

I think that this step of your explanation "…and the summand involving k in the rhs is F_{n-1}", is not straightforward. What about t dependence in summand? I mean…

F_{n-1} = \Sigma_{k=0}^{\infty}\left(f(n-1,k-t)x^{k-t}\right)

the LHS of the equality is independent of t, while that’s not the case with the RHS.

I know you can change variables k' = k-t and as k goes from 0 to \infty then k' will go from -t to \infty and maybe you can argue about terms from -t to 0 and discard them. Anyway what I’m saying is that in my opinion the explanation should include such considerations

Yes, you are right, I kinda took it for granted. I’ve included this exact same explanation in the editorial.

I thought this was a subtle enough detail that needn’t be mentioned explicitly, thanks for your comment.

1 Like