[Solution] Tokitsukaze and Permutations solution codeforces

Tokitsukaze and Permutations solution codeforces – Tokitsukaze has a permutation 𝑝p. She performed the following operation to 𝑝p exactly 𝑘k times: in one operation, for each 𝑖i from 11 to 𝑛1n−1 in order, if 𝑝𝑖pi > 𝑝𝑖+1pi+1, swap 𝑝𝑖pi𝑝𝑖+1pi+1. After exactly 𝑘k times of operations, Tokitsukaze got a new sequence 𝑎a, obviously the sequence 𝑎a is also a permutation.

[Solution] Tokitsukaze and Permutations solution codeforces

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 𝑣𝑖=𝑖1𝑗=1[𝑎𝑖<𝑎𝑗]vi=∑j=1i−1[ai<aj], where the value of [𝑎𝑖<𝑎𝑗][ai<aj] define as if 𝑎𝑖<𝑎𝑗ai<aj, the value is 11, otherwise is 00 (in other words, 𝑣𝑖vi is equal to the number of elements greater than 𝑎𝑖ai 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 998244353998244353.

[Solution] Tokitsukaze and Permutations solution codeforces

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. Each test case consists of two lines.

The first line contains two integers 𝑛n and 𝑘k (1𝑛1061≤n≤1060𝑘𝑛10≤k≤n−1) — the length of the permutation and the exactly number of operations.

The second line contains 𝑛n integers 𝑣1,𝑣2,,𝑣𝑛v1,v2,…,vn (1𝑣𝑖𝑖1−1≤vi≤i−1) — the value sequence 𝑣v𝑣𝑖=1vi=−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 106106.


For each test case, print a single integer — the number of different permutations modulo 998244353998244353.

[Solution] Tokitsukaze and Permutations solution codeforces


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


[Solution] Tokitsukaze and Permutations solution codeforces

In the first test case, only permutation 𝑝=[5,4,3,2,1]p=[5,4,3,2,1] satisfies the constraint condition.

In the second test case, there are 66 permutations satisfying the constraint condition, which are:

  • [3,4,5,2,1][3,4,5,2,1]  [3,4,2,1,5][3,4,2,1,5]  [3,2,1,4,5][3,2,1,4,5]
  • [3,5,4,2,1][3,5,4,2,1]  [3,4,2,1,5][3,4,2,1,5]  [3,2,1,4,5][3,2,1,4,5]
  • [4,3,5,2,1][4,3,5,2,1]  [3,4,2,1,5][3,4,2,1,5]  [3,2,1,4,5][3,2,1,4,5]
  • [4,5,3,2,1][4,5,3,2,1]  [4,3,2,1,5][4,3,2,1,5]  [3,2,1,4,5][3,2,1,4,5]
  • [5,3,4,2,1][5,3,4,2,1]  [3,4,2,1,5][3,4,2,1,5]  [3,2,1,4,5][3,2,1,4,5]
  • [5,4,3,2,1][5,4,3,2,1]  [4,3,2,1,5][4,3,2,1,5]  [3,2,1,4,5][3,2,1,4,5]

So after exactly 22 times of swap they will all become 𝑎=[3,2,1,4,5]a=[3,2,1,4,5], whose value sequence is 𝑣=[0,1,2,0,0]v=[0,1,2,0,0].


For Solution

Click here

Leave a Comment