Girl Permutation (Codeforces 1946E)
Tags: Math, number theory

Some permutation of length $$$n$$$ is guessed.You are given the indices of its prefix maximums and suffix maximums.Recall that a permutation of length $$$k$$$ is an array of size $$$k$$$ such that each integer from $$$1$$$ to $$$k$$$ occurs exactly once.Prefix maximums are the elements that are the maximum on the prefix ending at that element. More formally, the element $$$a_i$$$ is a prefix maximum if $$$a_i > a_j$$$ for every $$$j < i$$$.Similarly, suffix maximums are defined, the element $$$a_i$$$ is a suffix maximum if $$$a_i > a_j$$$ for every $$$j > i$$$.You need to output the number of different permutations that could have been guessed.As this number can be very large, output the answer modulo $$$10^9 + 7$$$.

Input: Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.The first line of each test case contains three integers $$$n, m_1$$$ and $$$m_2$$$ ($$$1 \le m_1, m_2 \le n \le 2 \cdot 10^5$$$) — the length of the permutation, the number of prefix maximums, and the number of suffix maximums, respectively.The second line of each test case contains $$$m_1$$$ integers $$$p_1 < p_2 < \ldots < p_{m_1}$$$ ($$$1 \le p_i \le n$$$) — the indices of the prefix maximums in increasing order.The third line of each test case contains $$$m_2$$$ integers $$$s_1 < s_2 < \ldots < s_{m_2}$$$ ($$$1 \le s_i \le n$$$) — the indices of the suffix maximums in increasing order.It is guaranteed that the sum of the values of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer on a separate line — the number of suitable permutations modulo $$$10^9 + 7$$$.

Note: The following permutations are suitable for the second set of input data:  $$$[1, 4, 3, 2]$$$  $$$[2, 4, 3, 1]$$$  $$$[3, 4, 2, 1]$$$ The following permutations are suitable for the sixth set of input data:  $$$[2, 1, 6, 5, 3, 4]$$$  $$$[3, 1, 6, 5, 2, 4]$$$  $$$[3, 2, 6, 5, 1, 4]$$$  $$$[4, 1, 6, 5, 2, 3]$$$  $$$[4, 2, 6, 5, 1, 3]$$$  $$$[4, 3, 6, 5, 1, 2]$$$  $$$[5, 1, 6, 4, 2, 3]$$$  $$$[5, 2, 6, 4, 1, 3]$$$  $$$[5, 3, 6, 4, 1, 2]$$$  $$$[5, 4, 6, 3, 1, 2]$$$ 

Sample Inputs:
6
1 1 1
1
1
4 2 3
1 2
2 3 4
3 3 1
1 2 3
3
5 3 4
1 2 3
2 3 4 5
20 5 4
1 2 3 4 12
12 13 18 20
6 2 3
1 3
3 4 6

Sample Outputs:
1
3
1
0
317580808
10

Solution (Python):
import sys
import math
input = sys.stdin.readline
MOD = int(1000000000.0 + 7)

def comb(n1, n2):
    if n1 == n2:
        return 1
    if n2 == 0:
        return 1
    f1 = 1
    f2 = 1
    f3 = 1
    for i in range(1, n1 + 1):
        if i == n2 + 1:
            f2 = f1
        if i == n1 - n2 + 1:
            f3 = f1
        f1 = f1 * i % MOD
    a = pow(f2 * f3 % MOD, -1, MOD)
    return f1 * a % MOD

def solve():
    (N, M1, M2) = map(int, input().split())
    L = list(map(int, input().split()))
    R = list(map(int, input().split()))
    if L[-1] != R[0]:
        return 0
    if L[0] != 1 or R[-1] != N:
        return 0
    if M1 > 1 and M2 > 1 and (L[-2] == R[1]):
        return 0
    ans = comb(N - 1, L[-1] - 1)
    cur = M1 - 2
    if M1 > 1:
        nums_left = L[-1] - 2
        i = L[-1] - 1
        while i > 1:
            if i == L[cur]:
                cur -= 1
            else:
                ans = ans * nums_left % MOD
            nums_left -= 1
            i -= 1
    nums_left = N - R[0] - 1
    if M2 > 1:
        cur = 1
        i = R[0] + 1
        while i < N:
            if i == R[cur]:
                cur += 1
            else:
                ans = ans * nums_left % MOD
            nums_left -= 1
            i += 1
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
mod = 10 ** 9 + 7
line = lambda : list(map(int, input().split()))

def choose(n, k, m):
    if n < 0 or k < 0 or k > n:
        return 0
    return fact[n] * invfact[k] * invfact[n - k] % m
fact = [1]
for i in range(2 * 10 ** 5):
    fact.append(fact[-1] * (i + 1) % mod)
invfact = [pow(fact[-1], -1, mod)]
for i in range(2 * 10 ** 5, 0, -1):
    invfact.append(invfact[-1] * i % mod)
invfact = invfact[::-1]
for _ in range(int(input())):
    (n, m1, m2) = line()
    p = line()
    s = line()
    if p[0] != 1 or p[-1] != s[0] or s[-1] != n:
        print(0)
    else:
        ans = choose(n - 1, p[-1] - 1, mod)
        for i in range(1, m1):
            ans = ans * fact[p[-i] - 2] * invfact[p[-i - 1] - 1] % mod
        ss = [n + 1 - e for e in s[::-1]]
        for i in range(1, m2):
            ans = ans * fact[ss[-i] - 2] * invfact[ss[-i - 1] - 1] % mod
        print(ans)

Solution (Python):
U = 1000000007

def pw(x, y):
    v = 1
    while y:
        if y & 1:
            v = v * x % U
        y >>= 1
        x = x * x % U
    return v
fac = [1]
for i in range(1, 200001):
    fac.append(fac[-1] * i % U)
inv = [0] * 200001
inv[200000] = pw(fac[200000], U - 2)
for i in range(199999, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % U
t = int(input())
for _ in range(t):
    (n, m1, m2) = [int(z) for z in input().split()]
    a1 = [int(z) for z in input().split()]
    a2 = [int(z) for z in input().split()]
    if a1[0] != 1 or a1[-1] != a2[0] or a2[-1] != n:
        print(0)
    else:
        m = a2[0]
        l = m - 1
        r = n - m
        v = fac[n - 1] * inv[l] * inv[r] % U
        for i in range(m1 - 2, -1, -1):
            dx = a1[i + 1] - a1[i] - 1
            v = v * fac[l - 1] * inv[l - 1 - dx] % U
            l = a1[i] - 1
        for i in range(m2 - 1):
            dx = a2[i + 1] - a2[i] - 1
            v = v * fac[r - 1] * inv[r - 1 - dx] % U
            r = n - a2[i + 1]
        print(v)