Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given two positive integers $N, K$, where $K ≤ N$. Your goal is to find the number of permutations of $\{1, 2, ..., N\}$ with exactly $K$ [inversions]. As the answer may be very large, you only need to find it modulo $2$.

------ Input: ------

The first line contains one integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains a single line of input, two integers $N, K$. 

------ Output: ------
For each test case, print one integer: the number of permutation of $N$ elements with $K$ inversions, modulo $2$.

------ Constraints  ------
$1 ≤ T ≤ 100$
$0 ≤ K ≤ N ≤ 2 \cdot 10^{10}$

------ Subtasks ------
10 points : $1 ≤ N ≤ 200$
10 points : $1 ≤ N ≤ 2000$
10 points : $1 ≤ N ≤ 200\,000$
10 points : $1 ≤ N ≤ 2\,000\,000$
60 points : $1 ≤ N ≤ 2 \cdot 10^{10}$

----- Sample Input 1 ------ 
11  

10 0  

10 1  

10 2   

10 3  

10 4  

10 5  

10 6  

10 7  

10 8  

10 9   

10 10
----- Sample Output 1 ------ 
1  

1  

0  

1  

0  

0  

0  

1  

1  

0  

0

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Combinatorics

Mathematics


Solutions:
tt = int(input())
for i in range(tt):
	(n, t) = map(int, input().split())
	count = 0
	if n == 0:
		print(0)
		continue
	if t == 0:
		print(1)
		continue
	z = n - 1 & t
	if z == 0:
		count = count + 1
	x = ((1 + 24 * t) ** 0.5 - 1) / 6
	y = x
	x = int(x)
	for j in range(1, x + 1):
		u = j * (3 * j - 1) // 2
		a = n + t - j - 1 - u
		b = t - j - u
		z = a - b & b
		if z == 0:
			count = count + 1
		a = a + j
		b = b + j
		z = a - b & b
		if z == 0:
			count = count + 1
	x2 = y + 1 / 3
	x2 = int(x2)
	for j in range(x + 1, x2 + 1):
		u = j * (3 * j - 1) // 2
		a = n + t - 1 - u
		b = t - u
		z = a - b & b
		if z == 0:
			count = count + 1
	if count % 2 == 1:
		print(1)
	else:
		print(0)


from sys import stdout, stdin
from collections import defaultdict, deque
import math
m = 115475
u = [0] * m
for i in range(m):
	u[i] = i * (3 * i - 1) // 2
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	temp = math.sqrt(1 / 36 + 2 * k / 3)
	temp += 5e-14
	lower = math.floor(temp - 1 / 6)
	upper = math.floor(temp + 1 / 6)
	(a, b, c) = (0, 0, 0)
	if n + k - 1 | k == n + k - 1:
		a = 1
	for i in range(1, lower + 1):
		(x, y) = (n - 1, k - u[i] - i)
		x += y
		if x | y == x:
			b = b ^ 1
	for i in range(1, upper + 1):
		(x, y) = (n - 1, k - u[i])
		x += y
		if x | y == x:
			c = c ^ 1
	print(a ^ b ^ c)