Valid Bitonic Permutations (Codeforces 1763D)
Tags: Math, combinatorics

You are given five integers $$$n$$$, $$$i$$$, $$$j$$$, $$$x$$$, and $$$y$$$. Find the number of bitonic permutations $$$B$$$, of the numbers $$$1$$$ to $$$n$$$, such that $$$B_i=x$$$, and $$$B_j=y$$$. Since the answer can be large, compute it modulo $$$10^9+7$$$.A bitonic permutation is a permutation of numbers, such that the elements of the permutation first increase till a certain index $$$k$$$, $$$2 \le k \le n-1$$$, and then decrease till the end. Refer to notes for further clarification.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The only line of each test case contains five integers, $$$n$$$, $$$i$$$, $$$j$$$, $$$x$$$, and $$$y$$$ ($$$3 \le n \le 100$$$ and $$$1 \le i,j,x,y \le n$$$). It is guaranteed that $$$i < j$$$ and $$$x \ne y$$$.

Output: For each test case, output a single line containing the number of bitonic permutations satisfying the above conditions modulo $$$10^9+7$$$.

Note: A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).An array of $$$n \ge 3$$$ elements is bitonic if its elements are first increasing till an index $$$k$$$, $$$2 \le k \le n-1$$$, and then decreasing till the end. For example, $$$[2,5,8,6,1]$$$ is a bitonic array with $$$k=3$$$, but $$$[2,5,8,1,6]$$$ is not a bitonic array (elements first increase till $$$k=3$$$, then decrease, and then increase again).A bitonic permutation is a permutation in which the elements follow the above-mentioned bitonic property. For example, $$$[2,3,5,4,1]$$$ is a bitonic permutation, but $$$[2,3,5,1,4]$$$ is not a bitonic permutation (since it is not a bitonic array) and $$$[2,3,4,4,1]$$$ is also not a bitonic permutation (since it is not a permutation).Sample Test Case DescriptionFor $$$n=3$$$, possible permutations are $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[2,1,3]$$$, $$$[2,3,1]$$$, $$$[3,1,2]$$$, and $$$[3,2,1]$$$. Among the given permutations, the bitonic permutations are $$$[1,3,2]$$$ and $$$[2,3,1]$$$.In the first test case, the expected permutation must be of the form $$$[2,?,3]$$$, which does not satisfy either of the two bitonic permutations with $$$n=3$$$, therefore the answer is 0.In the second test case, the expected permutation must be of the form $$$[?,3,2]$$$, which only satisfies the bitonic permutation $$$[1,3,2]$$$, therefore, the answer is 1.

Sample Inputs:
7
3 1 3 2 3
3 2 3 3 2
4 3 4 3 1
5 2 5 2 4
5 3 4 5 4
9 3 7 8 6
20 6 15 8 17

Sample Outputs:
0
1
1
1
3
0
4788

Solution (Python):
MOD = int(1000000000.0 + 7)

def inv(i):
    if i <= 1:
        return i
    return MOD - MOD // i * inv(MOD % i) % MOD
fact = [1]
modinv = [1]
for i in range(1, 1000):
    fact.append(fact[i - 1] * i % MOD)
    modinv.append(inv(fact[i]))

def c(n, k):
    if k > n or k < 0:
        return 0
    return fact[n] * modinv[n - k] * modinv[k] % MOD
t = int(input())
for tes in range(t):
    (n, i, j, x, y) = map(int, input().split())
    if x < y:
        i = n - i + 1
        j = n - j + 1
        (i, j) = (j, i)
        (x, y) = (y, x)
    if i == 1 and x == n:
        print(0)
        continue
    if x == n:
        ans = 1
        tot = n - 2
        h = j - i - 1
        ans = c(x - y - 1, h) * ans % MOD
        tot -= h
        ans = c(y - 1, n - j) * ans % MOD
        print(ans)
        continue
    ans = 0
    for me in range(2, i, +1):
        v = c(n - x - 1, i - me - 1)
        v = v * c(x - y - 1, j - i - 1) % MOD
        v = v * c(y - 1, n - j) % MOD
        ans = (ans + v) % MOD
    for me in range(i + 1, j):
        v = c(n - x - 1, me - i - 1)
        up = n - x - 1
        up -= me - i - 1
        if up > j - me - 1:
            continue
        v = v * c(x - y - 1, j - me - 1 - up) % MOD
        u = v
        if x - y - 1 - (j - me - 1 - up) > i - 1:
            continue
        v = v * c(y - 1, n - j) % MOD
        ans = (ans + v) % MOD
    print(ans)

Solution (Python):
N = 105
mod = int(1000000000.0 + 7)
T = int(input())
for _ in range(T):
    (n, I, J, X, Y) = map(int, input().split())
    if X > Y:
        (X, Y) = (Y, X)
        (I, J) = (J, I)
    f = [[0] * N for _ in range(N)]
    f[0][0] = 1
    for i in range(1, n):
        if i == X:
            if X >= I:
                f[i][I] += f[i - 1][I - 1]
            if X - (n - I + 1) >= 0:
                f[i][X - (n - I + 1)] += f[i - 1][X - (n - I + 1)]
        elif i == Y:
            if Y >= J:
                f[i][J] += f[i - 1][J - 1]
            if Y - (n - J + 1) >= 0:
                f[i][Y - (n - J + 1)] += f[i - 1][Y - (n - J + 1)]
        else:
            for j in range(i):
                f[i][j] = f[i][j] + f[i - 1][j]
                f[i][j + 1] += f[i - 1][j]
    ans = 0
    if Y != n:
        for i in range(1, n - 1):
            ans += f[n - 1][i]
    elif J != n and J != 1:
        ans = f[n - 1][J - 1]
    print(ans % mod)

Solution (Python):
mod = 1000000007

def check(pos, val):
    if pos == kk and val != ss:
        return False
    if pos == tt and val != pp:
        return False
    return True

def solve():
    global n, kk, tt, ss, pp
    (n, kk, tt, ss, pp) = map(int, input().split())
    global dp
    dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
    for i in range(2, n, 1):
        if check(i, n):
            dp[i][i] = 1
    for i in range(n, 0, -1):
        for j in range(i, n + 1):
            val = n - (j - i + 1)
            if check(i - 1, val):
                dp[i - 1][j] = (dp[i - 1][j] + dp[i][j]) % mod
            if check(j + 1, val):
                dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod
    print(int(dp[1][n]))
if __name__ == '__main__':
    __t = int(input())
    while __t > 0:
        __t -= 1
        solve()