Tokitsukaze and Permutations Codeforces Solution | Codeforces Problem Solution 2022

Tokitsukaze and Permutations Codeforces Solution | Codeforces Problem Solution 2022

F. Tokitsukaze and Permutations

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Tokitsukaze has a permutation 𝑝$p$. She performed the following operation to 𝑝$p$ exactly 𝑘$k$ times: in one operation, for each 𝑖$i$ from 1$1$ to 𝑛−1$n-1$ in order, if 𝑝𝑖$p_i$ > 𝑝𝑖+1$p_{i+1}$, swap 𝑝𝑖$p_i$, 𝑝𝑖+1$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 𝑣𝑖=∑𝑖−1𝑗=1[𝑎𝑖<𝑎𝑗]$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$1$, otherwise is 0$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.

Solution Click Below:-  CLICK HERE

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. 

Tokitsukaze and All Zero Sequence Codeforces Solution

[Solution] Tokitsukaze and Good 01-String

[Solution] Tokitsukaze and Good 01-String (hard version)

Tokitsukaze and Strange Inequality Codeforces Solution

Tokitsukaze and Meeting Codeforces Solution

Tokitsukaze and Two Colorful Tapes Codeforces Solution

Tokitsukaze and Permutations Codeforces Solution

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 998244353$998244353$.

Input

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

The first line contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑛≤106$1\le n\le {10}^6$; 0≤𝑘≤𝑛−1$0\le k\le n-1$) — the length of the permutation and the exactly number of operations.

The second line contains 𝑛$n$ integers 𝑣1,𝑣2,…,𝑣𝑛$v_1,v_2,\dots ,v_n$ (−1≤𝑣𝑖≤𝑖−1$-1\le v_i\le i-1$) — the value sequence 𝑣$v$. 𝑣𝑖=−1$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 106${10}^6$.

Output

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

Join Now for Solution:-