Tokitsukaze and Permutations

题意翻译

### 题目描述： 有一个长度为$n$的数组p，将执行$k$次操作 操作过程：对于$1$~$n$中，当$p_{i} > p_{i+1}$，则交换$p_{i}，p_{i+1}$ 经过$k$次操作之后，得到了一个新数组$a$，再定义数组$v$表示在$1$~$i-1$中比$a_{i}$大的个数 现在给定$v$，但是有可能其中的值为$-1$，这表示它的值并不确定 求有多少种$p$满足在$k$次操作后得到的$v$和给定确定值一致，结果取模$998244353$ ### 输入格式： 第一行一个正整数$t(1\le t \le 10^3)$表示测试用例数量 对于每组测试用例： 第一行两个正整数$n(1\le n \le 10^6),k(0 \le k \le n-1)$，表示长度，操作次数 第二行包含$n$个整数$v_{i}(-1\le v_{i}\le i-1)$，当$v_{i}=-1$时表示该值不确定 保证总和$n$在所有测试用例中不超过$10^6$ ### 输出格式： 对于每组测试用例： 一行一个正整数表示不同排列的数量取模$998244353$ ##### 输入样例： 3 5 0 0 1 2 3 4 5 2 -1 1 2 0 0 5 2 0 1 1 0 0 ##### 输出样例： 1 6 6

题目描述

Tokitsukaze has a permutation $ p $ . She performed the following operation to $ p $ exactly $ k $ times: in one operation, for each $ i $ from $ 1 $ to $ n - 1 $ in order, if $ p_i $ &gt; $ p_{i+1} $ , swap $ p_i $ , $ p_{i+1} $ . After exactly $ k $ times of operations, Tokitsukaze got a new sequence $ a $ , obviously the sequence $ a $ is also a permutation. After that, Tokitsukaze wrote down the value sequence $ v $ of $ a $ on paper. Denote the value sequence $ v $ of the permutation $ a $ of length $ n $ as $ v_i=\sum_{j=1}^{i-1}[a_i < a_j] $ , where the value of $ [a_i < a_j] $ define as if $ a_i < a_j $ , the value is $ 1 $ , otherwise is $ 0 $ (in other words, $ v_i $ is equal to the number of elements greater than $ a_i $ that are to the left of position $ i $ ). Then Tokitsukaze went out to work. There are three naughty cats in Tokitsukaze's house. When she came home, she found the paper with the value sequence $ v $ to be bitten out by the cats, leaving several holes, so that the value of some positions could not be seen clearly. She forgot what the original permutation $ p $ was. She wants to know how many different permutations $ p $ there are, so that the value sequence $ v $ of the new permutation $ a $ after exactly $ k $ operations is the same as the $ v $ written on the paper (not taking into account the unclear positions). Since the answer may be too large, print it modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. Each test case consists of two lines. The first line contains two integers $ n $ and $ k $ ( $ 1 \leq n \leq 10^6 $ ; $ 0 \leq k \leq n-1 $ ) — the length of the permutation and the exactly number of operations. The second line contains $ n $ integers $ v_1, v_2, \dots, v_n $ ( $ -1 \leq v_i \leq i-1 $ ) — the value sequence $ v $ . $ v_i = -1 $ means the $ i $ -th position of $ v $ can't be seen clearly. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, print a single integer — the number of different permutations modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

3
5 0
0 1 2 3 4
5 2
-1 1 2 0 0
5 2
0 1 1 0 0

输出样例 #1

1
6
6

说明

In the first test case, only permutation $ p=[5,4,3,2,1] $ satisfies the constraint condition. In the second test case, there are $ 6 $ permutations satisfying the constraint condition, which are: - $ [3,4,5,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [3,5,4,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [4,3,5,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [4,5,3,2,1] $ $ \rightarrow $ $ [4,3,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [5,3,4,2,1] $ $ \rightarrow $ $ [3,4,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ - $ [5,4,3,2,1] $ $ \rightarrow $ $ [4,3,2,1,5] $ $ \rightarrow $ $ [3,2,1,4,5] $ So after exactly $ 2 $ times of swap they will all become $ a=[3,2,1,4,5] $ , whose value sequence is $ v=[0,1,2,0,0] $ .