Counting Orders (Codeforces 1828C)
Tags: Others, combinatorics

You are given two arrays $$$a$$$ and $$$b$$$ each consisting of $$$n$$$ integers. All elements of $$$a$$$ are pairwise distinct.Find the number of ways to reorder $$$a$$$ such that $$$a_i > b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.Two ways of reordering are considered different if the resulting arrays are different.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the length of the array $$$a$$$ and $$$b$$$.The second line of each test case contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$. It is guaranteed that all elements of $$$a$$$ are pairwise distinct.The second line of each test case contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the array $$$b$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output: For each test case, output the number of ways to reorder array $$$a$$$ such that $$$a_i > b_i$$$ for all $$$1 \le i \le n$$$, modulo $$$10^9 + 7$$$.


Sample Inputs:
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144

Sample Outputs:
32
0
1
0
13824

Solution (Python):
import bisect
import sys
from collections import deque
from math import gcd
from collections import Counter

def find_gcd(numbers):
    result = numbers[0]
    for number in numbers[1:]:
        result = gcd(result, number)
    return result
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    n = int(input())
    a = sorted(readList())
    b = sorted(readList())
    a_bigger_count = 0
    permutaions = 1
    j = n - 1
    for i in range(n - 1, -1, -1):
        while j >= 0 and a[j] > b[i]:
            j -= 1
            a_bigger_count += 1
        permutaions *= a_bigger_count - (n - 1 - i)
        permutaions %= 1000000007
    return permutaions
    ''
for _ in range(int(input())):
    print(solve())

Solution (Python):
R = lambda : sorted(map(int, input().split()))
for _ in [0] * R()[0]:
    R()
    a = R()
    b = R() + [2000000000.0]
    r = 1
    i = j = 0
    for x in a:
        while x > b[j]:
            j += 1
        r = r * (j - i) % (10 ** 9 + 7)
        i += 1
    print(r)

Solution (Python):
for t in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort()
    m = 1000000000.0 + 7
    j = 0
    x = 1
    for i in range(n):
        while j < n and a[i] > b[j]:
            j += 1
        x = x * (j - i) % m
    print(int(x))