Problem:


Score : 300 points

Problem Statement

Given is an integer sequence D_1,...,D_N of N elements. Find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition:

For every integer i from 1 to N, the distance between Vertex 1 and Vertex i is D_i.

Notes

A tree of N vertices is a connected undirected graph with N vertices and N-1 edges, and the distance between two vertices are the number of edges in the shortest path between them.

Two trees are considered different if and only if there are two vertices x and y such that there is an edge between x and y in one of those trees and not in the other.

Constraints

1 \leq N \leq 10^5

0 \leq D_i \leq N-1

Input

Input is given from Standard Input in the following format:

N
D_1 D_2 ... D_N

Output

Print the answer.

Sample Input 1

4
0 1 1 2

Sample Output 1

2

For example, a tree with edges (1,2), (1,3), and (2,4) satisfies the condition.

Sample Input 2

4
1 1 1 1

Sample Output 2

0

Sample Input 3

7
0 3 2 1 2 2 1

Sample Output 3

24



Sample input:
4
0 1 1 2


Sample output:
2

Submission status: Accepted

Solution code:
import sys

n = int(input())
d = [int(x) for x in input().split()]

if d[0] != 0:
    print(0)
    sys.exit()

d.sort()

if d[1] == 0:
    print(0)
    sys.exit()
    
dd = []
c = 1
for i in range(1, n):
    if d[i-1]==d[i]:
        c += 1
    else:
        dd.append(c)
        c = 1
dd.append(c)

if len(dd) != d[-1]+1:
    print(0)
    sys.exit()

ans = 1
for i in range(1, len(dd)):
    ans *= dd[i-1] ** dd[i]

ans = ans % 998244353
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def solve(N,D):
    if D[0]:
        return 0

    try:
        _ = D[1::].index(0)
        return 0
    except:
        pass
    
    nums = Counter(D)
    nums = sorted(nums.items())
    if len(nums) != nums[-1][0]+1:
        return 0
        
    #print(nums)
    ans = 1
    for i in range(len(nums)-1):
        ans *= nums[i][1]**nums[i+1][1]
        ans %= 998244353
    return ans

def main():
    N = int(input())
    D = list(map(int, input().split()))
    
    print(solve(N,D))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
dl=list(map(int,input().split()))
MOD=998244353
if dl[0]>0:
    print(0)
    exit()
dist=[0]*(n)
for d in dl:
    dist[d]+=1
if dist[0]!=1:
    print(0)
    exit()
ans=1
flg=False
for i in range(1,n):
    if dist[i]>0:
        if flg:
            ans=0
            break
        else:
            ans*=dist[i-1]**dist[i]%MOD
    else:
        flg=True
print(ans%MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, D):
    if D[0] != 0:
        return 0
    C = Counter(D)
    if C[0] != 1:
        return 0
    ans = 1
    M = Mod(998244353)
    for i in range(max(D)):
        if C[i] == 0:
            return 0
        ans = M.mul(ans, M.pow(C[i], C[i+1]))
    return ans


def main():
    N = read_int()
    D = read_int_n()
    print(slv(N, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353

def main():
    N = int(input())
    D = [int(c) for c in input().split()]

    if D[0] != 0:
        print(0)
        sys.exit()

    for i in range(1, N):
        if D[i] >= N or D[i] == 0:
            print(0)
            sys.exit()

    dist_nums = {}
    for i in range(N):
        if dist_nums.get(D[i]) is None:
            dist_nums[D[i]] = 1
        else:
            dist_nums[D[i]] += 1

    ans = 1
    num = 1
    dist_nums = sorted(dist_nums.items(), key=lambda x: x[0]) # [(0, 1), (1, 2), (2, 1)]
    for i in range(1, len(dist_nums)):
        if dist_nums[i][0] == i:
            ans *= dist_nums[i - 1][1] ** dist_nums[i][1]
            num += dist_nums[i][1]
        else:
            break

    if num != N:
        print(0)
    else:
        print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = input().split()
D = [int(d) for d in D]

hantei = 1
if(D[0] != 0):
    print(0)
else:
    D = sorted(D[1:])
    if(D[-1]==1):
        print(1)
    else:
        n = 0
        k = 0
        mul = 1
        k_count_before = 1
        while(n<len(D)):
            k += 1
            k_count = 0
            
            while(n<len(D) and D[n]==k):
                k_count += 1
                n += 1

            if(k_count==0):
                mul = 0
                hantei = 0
                break
            else:

                mul *= k_count_before**k_count
                k_count_before = k_count

        print(mul%998244353)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l1=sorted(l)
m=l1[-1]
if l[0]!=0:
  print(0)
else:
  ld=[0 for i in range(m+1)]
  b=False
  for i in range(n):
    ld[l[i]]+=1
  for i in range(1+m):
    if ld[i]==0:
      b=True
  if ld[0]!=1:
    print(0)
  elif b:
    print(0)
  else:
    ans=1
    for i in range(1,m+1):
      num=ld[i-1]**ld[i]
      ans=(ans*num)%(998244353)
    print(ans%(998244353))

Submission status: Accepted

Solution code:
import collections

N = int(input())
D = list(map(int,input().split()))
D_counter = collections.Counter(D)
D_max = max(D)
ans = 1
if D[0] > 0:
    ans = 0
else:
    if D_counter[0] > 1:
        ans = 0
    for n in range(1,D_max+1):
        if D_counter[n] > 0:
            for d in range(D_counter[n]):
                ans = ans * D_counter[n-1]
                ans = ans % 998244353
        else:
            ans = 0
            break
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
d = list(map(int,input().split()))

ans = 1
if d[0] != 0 or sum(d) < n - 2 or sum(d) > (n * (n - 1) // 2) + 1:
    print(0)
else:
    l = [0] * (max(d) + 1)
    for i in range(n):
        l[d[i]] += 1

    if l[0] != 1:
        print(0)
    else:
        for j in range(1, len(l)):
            if l[j] == 0:
                ans = 0
                break
            else:
                x = l[j - 1] ** l[j] % mod
                ans *= x
                ans %= mod
        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
mod = 998244353


def pow_by_iter(a, x, n):
    acc = a
    for i in range(1, x):
        acc = (acc * a) % n
    return acc


d = Counter(D)
d_key = sorted(d.keys())
if D[0] != 0 or d[0] > 1:
    print(0)
    exit()


answer = 1

for i in range(1, len(d_key)):
    if d_key[i] != d_key[i - 1] + 1:
        print(0)
        exit()
    else:
        answer *= pow_by_iter(d[d_key[i - 1]], d[d_key[i]], mod)
        answer %= mod

print(answer)

Submission status: Accepted

Solution code:
import sys
N = int(input())
D = list(map(int, input().split()))

Ans = 0
number = 1
n_count = 0
b_count = 1

newD = sorted(D)
if N == 1:
  Ans = 1
  print(Ans)
  sys.exit()

if D[0] != 0 or newD[1] != 1:
  print(Ans)
  sys.exit()
else:
  
  for i in range(1,N):
    if newD[i] == number:
      n_count = n_count + 1
    elif newD[i] == number + 1:

      if number == 1:
        Ans = 1
        #print(Ans)
      else:
        Ans = Ans * (b_count ** n_count)
        if Ans > 998244353:
          Ans = Ans % 998244353
        #print(Ans)
        
      number = number + 1
      b_count = n_count
      n_count = 1
    else:
      Ans = 0
      print(Ans)
      sys.exit()

  if number == 1:
    Ans = 1
  else:
    Ans = Ans * (b_count ** n_count)
    Ans = Ans % 998244353
  print(Ans)

Submission status: Accepted

Solution code:
#B
import collections

N = int(input())
D = list(map(int, input().split()))
is_first_zero = True
if D[0] != 0:
    is_first_zero = False
if is_first_zero:
    c = sorted(collections.Counter(D).items(), key=lambda x:x[0])
    if len(c) == 2:
        res = 1
    for index, i in enumerate(c):
        ind = i[0]
        num = i[1]
        if ind == 0:
            if num != 1:
                is_first_zero = False
                break
        else:
            if ind != pre_ind + 1:
                is_first_zero = False
                break
            else:
                if index == 2:
                    res = pre_num ** num
                elif index > 2:
                    res = res * (pre_num ** num)
                #print(res)
        pre_ind = ind
        pre_num = num
                
if is_first_zero:
    print(res % 998244353)
else:
    print("0")

Submission status: Accepted

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    n = I()
    print(n // 2 - 1 if n % 2 == 0 else n // 2)
    return


# B
def B():
    n = I()
    d = LI()
    if d[0] != 0:
        print(0)
        return
    d.sort()
    if d[1] == 0:
        print(0)
        return
    cnt = []
    prenum = 1
    for i in range(1, max(d) + 1):
        num = bisect.bisect_right(d, i)
        if num - prenum == 0:
            print(0)
            return
        else:
            cnt.append(num - prenum)
            prenum = num
    ans = 1
    for i in range(1, max(d)):
        ans *= cnt[i - 1] ** cnt[i]
    print(ans % 998244353)
    return


# C
def C():
    return


# D
def D():
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    B()
    return


# Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N = INT()
A = LIST()

if A[0] != 0:
    print(0)
    exit()

C = Counter(A)
if C[0] > 1:
    print(0)
    exit()

depth = 0
ans = 1
prev = 1
for k, v in sorted(C.items()):
    if k != depth:
        print(0)
        exit()
    ans *= pow(prev, v, MOD)
    ans %= MOD
    depth += 1
    prev = v
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = [int(s) for s in input().split()]

maximum = max(D)
max_distance = [i+1 for i in range(maximum)]
count_list = [0 for i in range(maximum+1)]
for i in D:
  count_list[i] += 1
if D[0] != 0 or count_list[0] != 1:
  print(0)
  exit()

stock = 1
for i in max_distance:
  count_1 = count_list[i-1]
  count_2 = count_list[i]
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
error=0

if d[0]!=0:
	print(0)
else:
	d.sort()
	kotae=1
	kosulist=[]
	kazoe=1
	for i in range(1,n):
		if d[i]==d[i-1]:
			kazoe+=1
		else:
			kosulist.append(kazoe)
			kazoe=1
	kosulist.append(kazoe)
	
	kosukai=[1]
	for i in range(len(kosulist)-1):
		kosukai.append(kosukai[i]+kosulist[i+1])
	for i,a in enumerate(kosukai):
		if d[a-1]!=i:
			error=1
			break
			
	if error==0:		
		for i in range(len(kosulist)-1):
			kotae=kotae*((kosulist[i]**kosulist[i+1])%998244353)
		kotae=kotae%998244353
		print(int(kotae))
	else:
		print(0)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
R = max(D)
MOD = 998244353

cntD = Counter(D)
ans = 1
for i in range(1, R + 1):
    ans *= pow(cntD[i - 1], cntD[i], MOD)
    ans %= MOD

if D[0] == 0 and cntD[0] == 1 and all(cntD[i] >= 1 for i in range(R + 1)):
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
N=int(input())
ls=list(map(int,input().split()))
if ls[0]!=0:
  print(0)
  exit()
sls=sorted(ls)
if sls[1]==0:
  print(0)
  exit()
i=1
a=1
b=1
c=1
while i<N-1:
  if sls[i+1]==sls[i]:
    c+=1
  elif sls[i+1]==sls[i]+1:
    a=a*(b**c)
    b=c
    c=1
  else:
    a=0
    break
  i+=1
a=a*(b**c)
print(a%998244353)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))

C = [[] for _ in range(N)]
X = []
count = 0
ans = 1

for n in range(N):
    C[D[n]].append(D[n])

for i in range(1, max(D)):
    if len(C[i]) == 0:
        count += 1
        break

if count > 0:
    pass
elif D[0] != 0:
    count += 1
elif len(C[0]) != 1:
    count += 1
else:
    for j in range(1,max(D)+1):
        t = len(C[j-1]) ** len(C[j])
        X.append(t)
    for x in X:
        ans = x * ans
        ans = ans % 998244353
        
if count > 0:
    print(0)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
if a[0]!=0:
    print(0)
    exit()

b = [0]*n
for i in a: b[i]+=1

if b[0]!=1:
    print(0)
    exit()

ans = 1
i = 0
while i<n-1:
    if b[i]==0:
        if sum(b[i:])>0:
            print(0)
            exit()
        else:
            break
    ans *= b[i]**b[i+1]
    i += 1

print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
if D[0] > 0:
    print(0)
    exit(0)
cs = Counter(D)
if cs[0] > 1:
    print(0)
    exit(0)
count = 0
ans = 1
prev = 1
for i in range(N + 1):
    n = cs[i]
    if n == 0:
        if count == N:
            print(ans)
        else:
            print(0)
        exit(0)
    else:
        count += n
        ans = (ans * (prev ** n)) % 998244353
        prev = n

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))

X = 998244353

l_max = max(D)

def f():
    if D[0] != 0:
        print(0)
    
        return
    L = [0] * (l_max+1)
    for d in D:
        L[d] += 1 
    if L[0] != 1:
        print(0)
        return
    ans = 1
    L = [1] + L
    #print(L)

    for i in range(1, len(L)):
        if L[i] == 0:
            print(0)
            return
        ans = ans * (L[i-1] ** L[i])
    print(ans % X)
    
f()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
N = int(input())
D = [int(i) for i in input().split()]
if D[0] != 0:
    print(0)
    sys.exit()
D.sort()
if D[1] == 0:
    print(0)
    sys.exit()
a = Counter(D)
a = dict(sorted(a.items(), key=lambda x:x[0]))
ans = 1
mod = 998244353
backnumber = 1
for i, (x, y) in enumerate(a.items()):
    if i != x:
        print(0)
        sys.exit()
    if i != 0:
        ans *= backnumber**y
        ans = ans % mod
    backnumber = y
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
D = list(map(int,input().split()))

set_D = set(D)
c = collections.Counter(D)

sum = 1
if D[0] != 0 or D.count(0) > 1:
  print(0)
elif len(set_D)-1 == max(set_D):
  for i in range(len(set_D)):
    if i >= 1:
      sum *= c[i-1]**c[i]
  q, mod = divmod(sum, 998244353)
  print(mod)
else:
  print(0)

Submission status: Accepted

Solution code:
import collections
def counter_list(A):
  counter = collections.Counter(A)
  counter =  [list(e) for e in counter.items()]
  counter.sort() #sortしたい場合はつける
  return counter

N = int(input())
D = list(map(int,input().split()))
#print(D)

#ans = ans*(D[i][1]**D[i+1][1]) (mod 998244353)
if(D[0] != 0): ans = 0 #一番最初が0でないなら
else: 
  D = counter_list(D) # [[0,1],[1,3],...] → 0:1個,1:3個,...
  if(D[0][1] != 1):
    ans = 0
  else:
   ans = 1
   for i in range(len(D)-1):
      if(D[i+1][0] - D[i][0] != 1):
        ans = 0
        break
      a = D[i][1]%998244353
      b = D[i+1][1]
      ans = ans%998244353
      ans = ans*(a**b)
      ans = ans%998244353
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

mod = 998244353
from collections import Counter

def main():
  n = ni()
  d = na()

  if d[0] != 0:
    print(0)
    return
  
  pre = 0
  for dd in set(d[1:]):
    if dd - pre > 1 or dd == 0:
      print(0)
      return
    pre = dd

  dic = {}
  for dd in d:
    if dd in dic:
      dic[dd] += 1
    else:
      dic[dd] = 1

  ans = 1
  t = sorted(dic.items(), key = lambda x: x[0])
  for i in range(1, len(t) - 1):
    x = (t[i][1] ** t[i+1][1]) % mod
    ans *= x
    ans %= mod
  print(ans % mod)
 

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import numpy as np
import collections
import sys
N  = int(input())
Ds = np.array(list(map(int, input().split(' '))))
if Ds[0] != 0:
    print(0)
    sys.exit()
if np.any(Ds[1:] == 0):
    print(0)
    sys.exit()

uniq = np.unique(Ds)
uniq.sort()

if not np.all(uniq == np.arange(uniq.min(), uniq.max() + 1)):
    print(0)
    sys.exit()
C = collections.Counter(Ds)
counts = 1
for i in range(1, uniq.max() + 1):
    counts *= C[i-1] ** C[i]
print(counts % 998244353)

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
A = [int(x) for x in input().split()]

if A[0] != 0:
    print(0)
else:
    L = [0]*(n+1)
    for i in range(n):
        L[A[i]] += 1

    if L[0]!=1:
        print(0)
    else:
        ans = 1
        for i in range(1,n+1):
            if L[i]>0:
                for k in range(L[i]):
                    ans *= L[i-1]
                    ans %= mod
            else:
                nxt = i
                break
        for j in range(nxt,n+1):
            if L[j] != 0:
                print(0)
                break
        else:
            print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
else:
    D = D[1:]
    C = [0]*N
    m = max(D)
    for d in D:
        C[d] += 1
    if C[0] != 0 or 0 in C[1: m + 1]:
        print(0)
    else:
        res = 1
        i = 1
        for i in range(1, m):
            res *= (C[i]**C[i + 1])%998244353
        print(res%998244353)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
D = [int(x) for x in stdin.readline().rstrip().split()]

if D[0] > 0:
    print(0)
    exit()
D.sort()

ans = 1
mod = 998244353
b = 1

temp = 1
for i in range(1, N):
    if D[i] == 0:
        print(0)
        exit()
    if D[i] - D[i - 1] > 1:
        print(0)
        exit()
    if D[i] != D[i - 1]:
        b = temp
        temp = 1
    else:
        temp += 1
    ans *= b
    ans %= mod

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))

if D.pop(0):
  print(0)
else:
  C = Counter(D)
  if 0 in C:
    print(0)
  else:
    count = 1
    for i in range(2, max(C)+1):
      if i not in C:
        print(0)
        break
      count *= C[i-1]**C[i]
      count %= 998244353
    else:
      print(count)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
D = list(map(int, input().split()))
p = 998244353

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

count_dict = sorted(Counter(D).items(), key=lambda x:x[0])
count_list = list(dict(count_dict).values())

if len(count_list) == max(D) + 1 and not 0 in D[1:]:
    ans = 1
    for i in range(len(count_list)):
        if i == 0:
            if D[0] == 0:
                pass
            else:
                ans = 0
                break
        else:
            ans *= power_func(count_list[i - 1], count_list[i], p)
else:
    ans = 0

ans %= p
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
c = [0]*(N + 1)
a = 0
ans = 1
temp = 0
pre = 1
mod = 998244353
c = 1

if D[0] != 0:
    print(0)
    a = 1

if a == 0:
    D = sorted(D)
    for i, d in enumerate(D):
        if i == 0:
            continue
        if d == 0:
            print(0)
            a = 1
            break
        if temp != d:
            if (d - temp) != 1:
                print(0)
                a = 1
                break
            ans *= pre ** c

            temp = d
            pre = c
            c = 1
        else:
            c += 1

        if i == N-1:
            ans *= pre ** c
    if a == 0:
        print(ans%mod)

Submission status: Accepted

Solution code:
_,*D=map(int,open(0).read().split());a=D[0]<1;M=[0]*-~max(D)
for d in D:M[d]+=1
for m,n in zip(M,M[1:]):a*=m**n
print((M[0]<2)*a%998244353)

Submission status: Accepted

Solution code:
n= int(input())
d= list(map(int, input().split()))
y=(d[0]!=0)
d.sort()
x=[0]*(d[n-1]+1)
k=0
ans=False
for i in range(n):
    if d[i]==k:
        x[k]+=1
    elif d[i]==k+1:
        k+=1
        x[k]+=1
    else:
        ans=True
    #print(ans)
#print(d)
#print(x)
if ans or x[0]>=2 or y:
    print(0)
else:
    a=1
    for i in range(d[n-1]):
        a*=(x[i]**x[i+1])
    print(a%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D.sort()
count = Counter(D)
if count[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, D[-1] + 1):
    if i not in count:
        print(0)
        exit()
    ans *= count[i-1] ** count[i]
print(ans % 998244353)

Submission status: Accepted

Solution code:
d = 998244353

num = int(input())

l = list(map(int, input().split()))


flag = True

if l[0] != 0:
  flag = False

ll = set(l)

for i in range(max(ll)):
  if i + 1 not in ll:
    flag = False

a = [0 for i in range(max(ll))]

for x in l[1:]:
  if x == 0:
    flag = False
    break
  a[x-1] += 1


ans = 1

for i in range(len(a)-1):
  ans *= a[i] ** a[i+1]


if flag:
  print(ans % d)
else:
  print(0)

Submission status: Accepted

Solution code:
N = int(input().strip())
D = list(map(int, input().strip().split(" ")))
d = list(set(D))

if D[0] != 0:
    print(0)
    exit()
if min(d) > 0 or max(d) >= len(d):
    print(0)
    exit()

c = 1
x = [0] * len(d)
for i in D:
    x[i] += 1
if x[0] != 1:
    print(0)
    exit()
for i in range(1,len(d)):
    c *= x[i-1]**x[i]

print(c % 998244353)

Submission status: Accepted

Solution code:
_,*D=map(int,open(0).read().split());a=1;M=[0]*-~max(D)
for d in D:M[d]+=1
for m,n in zip(M,M[1:]):a*=m**n
print((D[0]<1)*(M[0]<2)*a%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(i) for i in input().split()]
a = sorted(d)
checkZero = False
if(d[0] != 0):
    checkZero = True
for i in range(1,len(d)):
    if(d[i] == 0):
        checkZero = True

if(checkZero):
    print(0)
else:
    start = 0
    counta = 0
    countb = 1
    ans = 1
    for i in a:
        if(start == i):
            counta += 1
        elif(i - start > 1):
            ans = 0
        else:
            ans *= countb ** counta
            start = i
            countb = counta
            counta = 1
    ans *= countb ** counta
    print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(x) for x in input().split(' ')]

m = {}
for item in d:
    if item in m:
        m[item] += 1
    else:
        m[item] = 1

if d[0] == 0 and m[0] == 1:
    prev = 1
    s = 1
    visited = 1
    for i in range(1, 10 ** 5):
        if not i in m:
            break
        v = m[i]
        visited += v

        s *= (prev ** v)
        s = s % 998244353
        prev = v
    if visited != n:
        s = 0
else:
    s = 0

print(s)

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))

mod=998244353

if D[0]!=0:
    print(0)
    exit()

n=[0]*N
n[0]=1
for i in range(1,N):
    if D[i]==0:
        print(0)
        exit()
    n[D[i]]+=1

ans=1
cnt=n[0]+n[1]
for i in range(2,N):
    if n[i]==0:
        if cnt!=N:
            print(0)
            exit()
        else:
            break
    ans=ans*n[i-1]**n[i]
    ans=ans%mod
    cnt=cnt+n[i]
print(ans)

Submission status: Accepted

Solution code:
M = 998244353

N = int(input())
d_list = list(map(int, input().split()))

def check():
	if d_list[0] != 0:
		print(0)
		return
	d_list.sort()
	d_counts = []
	prev_d = -1
	for d in d_list:
		if prev_d == d:
			d_counts[prev_d] += 1
		elif prev_d + 1 == d:
			d_counts.append(1)
			prev_d = d
		else:
			print(0)
			return
	count = 1
	prev_c = d_counts.pop(0)
	if prev_c != 1:
		print(0)
	else:
		for c in d_counts:
			count = (count * pow(prev_c, c, M)) % M
			prev_c = c
		print(count)

check()

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))

if d[0] != 0:
  print(0)
  exit()

ans=1

a=[0]*(n+1)

for i in d:
  a[i] += 1

if a[0] != 1:
  print(0)
  exit()

for j in range(n):
  if j!=0 and a[j] == 0:
    for k in range(j+1,n):
      if a[k] != 0:
        print(0)
        exit()
    break
  else:
    ans*=(a[j]**a[j+1])
    ans%=998244353

print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
    print(0)
    sys.exit()
d.sort()
mx=d[-1]
count=[0]*(mx+1)
MOD=998244353
for i in range(n):
    count[d[i]]+=1
c=1
#print(d,count)
if count[0]!=1:
    print(0)
    sys.exit()
for i in range(1,mx+1):
    c*=pow(count[i-1],count[i],MOD)
    c%=MOD
print(c)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
mod = 998244353
mN = max(D)
count = [0] * (mN + 1)
for i in range(N):
    count[D[i]] += 1
if count[0] != 1 or D[0] != 0:
    print(0)
elif mN == 0:
    print(1)
else:
    ans = 1
    for i in range(1, len(count)):
        if count[i]:
            ans = (ans * (count[i - 1] ** count[i])) % mod
        else:
            print(0)
            exit()
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0: 
    print(0)
    exit()
    
D = Counter(D)

ans = 1
if D[0] > 1: 
    print(0)
    exit()

for i in range(N):
    ans = (ans * D[i] ** D[i+1]) % 998244353

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
D = list(map(int,input().split()))
if D[0] != 0:
    print(0)
    exit()
D = D[1:]
DD = Counter(D)
if DD[0] != 0:
    print(0)
    exit()
#print(DD)
MOD = 998244353
ans = 1
if len(DD) == 1:
    print(1)
    exit()
for i in range(2,len(DD)+1):
    ans *= pow(DD[i-1],DD[i],MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def resolve():
    n = int(input())
    d = list(map(int, input().split()))
    c = Counter(d)
    m = sorted(c)[-1]
    ans = 1
    if d[0] != 0 or c[0] != 1:
        print(0)
        return
    for i in range(1, m + 1):
        if not i in c:
            print(0)
            return
        ans *= c[i - 1] ** c[i]
        ans %= 998244353
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
D = [int(i) for i in input().split()]

key = max(D) + 1
count_list = [0] * key

for i in range(N):
    count_list[D[i]] += 1

counter = 1
if 0 in count_list:
    counter = 0

if count_list[0] != 1:
    counter = 0

if D[0] != 0:
    counter = 0 

for i in range(1, key - 1):
    counter *= count_list[i]**count_list[i + 1]

print(counter%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))

if d[0] != 0:
    print(0)
    exit()

d.sort()

if d[1] != 1:
    print(0)
    exit()

i = 1
dis = 1
sep = [0] * (10 ** 5)
sep[0] = 1
ans = 1
while i < n:
    if d[i] != dis:
        print(0)
        exit()
    while i < n and d[i] == dis:
        sep[dis] += 1
        i += 1
    ans *= sep[dis-1] ** sep[dis]
    ans %= 998244353
    dis += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
D = list(map(int, input().split()))
if D[0] > 0:
    print(0)
    exit()

D = D[1:]
for d in D:
    if d == 0:
        print(0)
        exit()

mod = 998244353
X = defaultdict(int)

for d in D:
    X[d] += 1

M = max(D)
ans = 1
for i in range(1, M):
    if X[i] == 0:
        ans = 0
        break
    ans *= pow(X[i], X[i+1], mod)
    ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
N=int(input())
E=list(map(int, input().split()))
k=max(E)
D={}
for i in range(k+1):
    D[i]=0
for i in range(N):
    D[E[i]]+=1
    

ans=1
for i in range(1,k+1):
    ans*=D[i-1]**D[i]
if D[0]==1 and E[0]==0:
    print(ans%998244353)
else:
    print(0)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
Dlist = list(map(int, input().split()))

INF = 998244353

if Dlist[0] != 0:
    print(0)

else:
    D_max = max(Dlist)
    cnt = [0] * (D_max + 1)

    dic = Counter(Dlist)
    for k, v in dic.items():
        cnt[k] = v

    ans = cnt[0]

    if ans != 1:
        print(0)

    else:
        for i in range(D_max):
            ans = ans * (((cnt[i] % INF) ** cnt[i+1]) % INF)
            ans = ans % INF
        
        print(ans % INF)