309945: CF1763D. Valid Bitonic Permutations
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Valid Bitonic Permutations
题意翻译
给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$,如果它满足如下两个条件,则我们称它是一个双调排列: 1. 这个数列是一个 $1 \sim n$ 的排列(也就是说对于任意一个整数 $1 \le i \le n$,数列中都存在一个等于 $i$ 的元素) 2. 存在一个下标 $k(2 \le k \le n-1)$,使得 $a_1$ 到 $a_k$ 是单调递增的,$a_k$ 到 $a_n$ 是单调递减的。 现在给你五个整数 $n, i, j, x, y$,它们表示数列长度为 $n$,$a_i = x$,$a_j = y$,求满足该条件的双调排列的个数。 由于满足条件的双调排列数可能很大,所以你只需要输出排列数模 $10^9 + 7$ 的结果即可。题目描述
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.输入输出格式
输入格式
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 $ .
输出格式
For each test case, output a single line containing the number of bitonic permutations satisfying the above conditions modulo $ 10^9+7 $ .
输入输出样例
输入样例 #1
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
输出样例 #1
0
1
1
1
3
0
4788