Fancy Stack

题意翻译

### 题目描述 有 $n$ 块木块（$n$ 为偶数），长度依次为 $a_1,a_2,…,a_n$（可能会相同），现在想要把它们叠成一叠，且满足以下条件（令这一叠木块从上到下的长度依次为 $b_1,b_2,…,b_n$ 且 $b$ 数组为 $a$ 数组的一个排列）： - 从上往下的第二块木块长度严格大于第一块，之后的每一块木块交替严格小于或严格大于上一个块，也就是说，满足 $b_1<b_2>b_3<b_4>…>b_{n-1}<b_n$； - 从上往下的偶数号木块的长度严格递增，即 $b_2<b_4<b_6<…<b_n$。 两种叠法是不同的当且仅当对应的 $b_1,b_2,…,b_n$ 有至少有一项不同。 请求出满足以上两个条件的叠法的种数，对 $998244353$ 取模。 ### 输入格式 每个测试点有多组数据。第一行读入一个正整数 $t$ 表示数据组数（$1\le t\le 2500$）。接下来依次读入 $t$ 组数据： 每组数据的第一行一个正整数 $n$ 表示木块数（$2\le n\le 5000$ 且为偶数）。 第二行 $n$ 个正整数 $a_1,a_2,…,a_n$ 依次表示每块木块的长度且 $1\le a_1\le a_2\le …\le a_n\le n$。 所有数据的 $n$ 之和不超过 $5000$。 ### 输出格式 对于每组数据，输出方案数，对 $998244353$ 取模。

题目描述

Little Fiona has a collection of $ n $ blocks of various sizes $ a_1, a_2, \ldots, a_n $ , where $ n $ is even. Some of the blocks can be equal in size. She would like to put all these blocks one onto another to form a fancy stack. Let $ b_1, b_2, \ldots, b_n $ be the sizes of blocks in the stack from top to bottom. Since Fiona is using all her blocks, $ b_1, b_2, \ldots, b_n $ must be a permutation of $ a_1, a_2, \ldots, a_n $ . Fiona thinks the stack is fancy if both of the following conditions are satisfied: - The second block is strictly bigger than the first one, and then each block is alternately strictly smaller or strictly bigger than the previous one. Formally, $ b_1 < b_2 > b_3 < b_4 > \ldots > b_{n-1} < b_n $ . - The sizes of the blocks on even positions are strictly increasing. Formally, $ b_2 < b_4 < b_6 < \ldots < b_n $ (remember that $ n $ is even). Two stacks are considered different if their corresponding sequences $ b_1, b_2, \ldots, b_n $ differ in at least one position. Fiona wants to know how many different fancy stacks she can build with all of her blocks. Since large numbers scare Fiona, find this number modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

Each input contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2500 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ — the number of blocks at Fiona's disposal ( $ 2 \le n \le 5000 $ ; $ n $ is even). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ — the sizes of the blocks in non-decreasing order ( $ 1 \le a_1 \le a_2 \le \dotsb \le a_n \le n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

输出格式

For each test case, print the number of ways to build a fancy stack, modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

2
4
1 2 3 4
8
1 1 2 3 4 4 6 7

输出样例 #1

2
4