Small Permutation Problem (Easy Version) (Codeforces 1909F1)
Tags: Math, combinatorics

Andy Tunstall - MiniBoss⠀In the easy version, the $$$a_i$$$ are in the range $$$[0, n]$$$; in the hard version, the $$$a_i$$$ are in the range $$$[-1, n]$$$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.You are given an integer $$$n$$$ and an array $$$a_1, a_2 \dots, a_n$$$ of integers in the range $$$[0, n]$$$.A permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$ is good if, for each $$$i$$$, the following condition is true:   the number of values $$$\leq i$$$ in $$$[p_1, p_2, \dots, p_i]$$$ is exactly $$$a_i$$$. Count the good permutations of $$$[1, 2, \dots, n]$$$, modulo $$$998\,244\,353$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$), which describe the conditions for a good permutation.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing the number of good permutations, modulo $$$998\,244\,353$$$.

Note: In the first test case, the only good permutation is $$$[1, 2, 3, 4, 5]$$$.In the second test case, there are $$$4$$$ good permutations: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. For example, $$$[2, 1, 5, 6, 3, 4]$$$ is good because:   $$$a_1 = 0$$$, and there are $$$0$$$ values $$$\leq 1$$$ in $$$[p_1] = [2]$$$;  $$$a_2 = 2$$$, and there are $$$2$$$ values $$$\leq 2$$$ in $$$[p_1, p_2] = [2, 1]$$$;  $$$a_3 = 2$$$, and there are $$$2$$$ values $$$\leq 3$$$ in $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;  $$$a_4 = 2$$$, and there are $$$2$$$ values $$$\leq 4$$$ in $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;  $$$a_5 = 4$$$, and there are $$$4$$$ values $$$\leq 5$$$ in $$$[p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]$$$;  $$$a_6 = 6$$$, and there are $$$6$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]$$$. In the third test case, there are no good permutations, because there are no permutations with $$$a_6 = 5$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$.

Sample Inputs:
5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

Sample Outputs:
1
4
0
0
532305727

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a) = (readInt(), [0] + readList())
    dp = 1
    for i in range(n):
        if a[i] > i:
            return 0
        if a[i + 1] == a[i]:
            continue
        elif a[i + 1] == a[i] + 1:
            dp *= 2 * (i - a[i]) + 1
            dp %= m
        elif a[i + 1] == a[i] + 2:
            dp *= (i - a[i]) ** 2
            dp %= m
        else:
            return 0
    return dp if a[-1] == n else 0
m = 998244353
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
import io
import os
from string import *
from re import *
from collections import *
from heapq import *
from bisect import *
from copy import *
from random import *
from itertools import *
from functools import *
from typing import *
MOD = 998244353
inf = 1 << 60

def solve():
    n = read_int()
    A = read_int_list()
    (cnt, res, pre) = (0, 1, 0)
    for cur in A:
        d = cur - pre
        if d == 0:
            cnt += 1
        elif d == 1:
            res *= cnt + cnt + 1
        elif d == 2:
            res *= cnt * cnt
            cnt -= 1
            if cnt < 0 or res == 0:
                return 0
        else:
            return 0
        res %= MOD
        pre = cur
    return 0 if cnt else res

def main():
    T = 1
    T = read_int()
    for t in range(T):
        print(solve())
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

def read_int_tuple():
    return map(int, input().split())

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys, math, random
from typing import Tuple, List, Mapping
from functools import reduce
MOD = 998244353
T = int(input())
for tt in range(T):
    N = int(input())
    A = list(map(int, input().split()))

    def solve():
        (pa, left, pcnt) = (0, 0, 1)
        for i in range(N):
            a = A[i]
            da = a - pa
            if da == 0:
                left += 1
            elif da == 1:
                cnt = pcnt + pcnt * left * 2
                pcnt = cnt
            elif da == 2:
                if left <= 0:
                    return 0
                cnt = left * left * pcnt
                left -= 1
                pcnt = cnt
            else:
                return 0
            pa = a
            pcnt %= MOD
        if left != 0:
            return 0
        return pcnt
    res = solve()
    print(res)