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';
}
}