Tokitsukaze and Permutations (Codeforces 1678F)
Tags: Math, dp

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

Input: 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$$$.

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

Note: 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]$$$.

Sample Inputs:
3
5 0
0 1 2 3 4
5 2
-1 1 2 0 0
5 2
0 1 1 0 0

Sample Outputs:
1
6
6

Solution (Python):
MOD = 998244353

def solve():
    (n, k) = map(int, input().split())
    v = list(map(int, input().split()))
    if k > 0 and sum((1 for x in v[-k:] if x > 0)) > 0:
        print('0')
        return
    ans = 1
    for i in range(2, k + 1):
        ans = ans * i % MOD
    for i in range(n - k):
        if v[i] == -1:
            ans = ans * (i + k + 1) % MOD
        if v[i] == 0:
            ans = ans * (k + 1) % MOD
    print(ans)
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
MOD = 998244353

def solve():
    (n, k) = map(int, input().split())
    v = list(map(int, input().split()))
    if k > 0 and sum(v[-k:]) > 0:
        print('0')
        return
    ans = 1
    for i in range(2, k + 1):
        ans = ans * i % MOD
    for i in range(n - k):
        if v[i] == -1:
            ans = ans * (i + k + 1) % MOD
        if v[i] == 0:
            ans = ans * (k + 1) % MOD
    print(ans)
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
import sys
import math

def dc(x):
    return int(x) - 1
M = 998244353
input = sys.stdin.readline
t = int(input())

def test():
    R = 1
    for i in range(k):
        R = R * (i + 1) % M
        if v[n - 1 - i] > 0:
            return 0
    for i in range(k, n):
        if v[i - k] > i - k:
            return 0
        if v[i - k] == -1:
            R = R * (i + 1) % M
        if k > 0:
            if v[i - k] == 0:
                R = R * (k + 1) % M
    return R
for _test_ in range(t):
    (n, k) = map(int, input().split())
    v = list(map(int, input().split()))
    print(test())