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:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
D = read_ints()

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


# 飛んだらアウト
# 個数を数えてどうにかする
# D.sort()
# if D[1] == 0:
#     print(0)
#     exit()

# now = 0
# cnt = 0
# ans = 1
# pre_cnt = 0
# for d in D:
#     if d == now + 1:
#         ans *= cnt
#         pre_cnt = now
#         now = d
#         cnt = 0
#     elif d == now:
#         cnt += 1


from collections import Counter
dic = Counter(D)
ans = 1

if dic[0] != 1:
    print(0)
    exit()
# print(dic)
for i in range(max(D)):
    # もし連続してなかったらだめ
    try:
        dic[i + 1]
    except:
        print(0)
        exit()

    ans *= dic[i]**dic[i + 1]
    if ans > 998244353:
        ans = ans % 998244353

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ds=[int(i) for i in input().split()]
counts={}

if ds[0]!=0:
  ans=0

else:  
    for i in range(1,n):
      if ds[i] not in counts:
        counts[ds[i]]=1
      else:
        counts[ds[i]]+=1
    c=0
    for i in range(1,len(counts)+1):
      if i in counts:
        c+=1
    if c==len(counts):
      ans=1
      for i in range(1,len(counts)):
          x=(counts[i]**counts[i+1])%998244353
          ans*=x
          ans%998244353
    else:
      ans=0

print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
nc = [0]*(max(d)+1)
for i in range(0,n):
    nc[d[i]]+=1
if d[0]==0 and nc[0]==1 and nc.count(0)==0:
    ans = 1
    for i in range(1,len(nc)):
        ans *= nc[i-1]**nc[i]
        ans = ans%998244353
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
mod=998244353

N=int(input())
L=[0 for i in range(N)]
D=list(map(int,input().split()))
#print(D)
if D[0]!=0:
    print(0)
    exit()
for i in range(N):
    L[D[i]]+=1
#print(L)

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

ans=1
cnt=1
for i in range(1,N):
    ans*=pow(L[i-1],L[i],mod)
    cnt+=L[i]
    #print(ans,cnt)
    if cnt==N:
        break
print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
D=list(map(int,input().split()))
T=[[] for _ in range(max(D)+1)]
for i in range(n):
    T[D[i]].append(i+1)
if T[0]!=[1]:
    print(0)
    exit()
a=1
for j in range(1,len(T)):
    if T[j]==[]:
        print(0)
        exit()
    else:
        a*=len(T[j-1])**len(T[j])
        a%=998244353
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
n = int(input())
D = list(map(int,input().split()))
if (D[0] != 0):
  print(0)
  sys.exit(0)
c = Counter(D)
if (c[0] > 1):
  print(0)
  sys.exit(0)
ans = 1
for i in range(1,max(D)+1):
  ans *= c[i-1]**c[i]
print(ans % 998244353)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
mod = 998244353
ans = 1



n = int(readline())
d = list(map(int, readline().split()))

import collections
d_count = collections.Counter(d)

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

for i in range(n):
     ans = ans * (d_count[i] ** d_count[i+1]) % mod
     
     if d_count[i] == 0 and d_count[i+1] != 0:
         print(0)
         sys.exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
if (D[0]!=0) or (0 in D[1:]):
  print(0)
else:
  mapping = dict()
  max_ = 0
  for n in D[1:]:
    if n in mapping:
      mapping[n]+=1
    else:
      mapping[n]=1
      if max_ < n :
        max_ = n
  ans=1
  for i in range(1,max_):
    if (i in mapping) and (i+1 in mapping):
      ans *= mapping[i]**(mapping[i+1])
    else:
      ans = 0
      break
  print(ans % 998244353)

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 998244353

N = int(input())
D = [int(_) for _ in input().split()]
if D[0] != 0:
    print(0)
    exit()

counter = Counter(D)
if counter[0] != 1:
    print(0)
    exit()
max(D)
cnt = 0
ans = 1
pre = 1

for i in range(1, max(D) + 1):
    if counter[i] == 0:
        print(0)
        exit()
    ans *= (pre ** counter[i]) % MOD
    ans = ans % MOD
    pre = counter[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
MOD = 998244353  # type: int

def solve(N: int, D: "List[int]"):
    if D[0] != 0:
        print(0)
        return 
    
    for i in range(1,N):
        if D[i]==0:
            print(0)
            return 

    ## 階層が飛んでるものを除く
    D.sort()
    counter = Counter(D).items()
    answer = 1
    prev_node_count = 1
    layer = 0
    for c in counter:
        if layer == c[0]: 
            answer*=prev_node_count**c[1]
            prev_node_count = c[1]
            layer+=1
        else:
            print(0)
            return 
    
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

n = int(input())
d_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(d_ls)
res = 1
if d_ls[0] != 0 or ct[0] > 1:
    print(0)
else:
    for i, count in sorted(ct.items(), key=lambda x:x[1]):
        if i == 0:
            continue
        res = (res * (ct[i-1] ** count)) % 998244353
    print(res)

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(10**6+10)
N=int(input()) 
d=list(map(int, input().split())) 

  
  
c = collections.Counter(d)
c = dict(collections.Counter(d))

if d[0] != 0 or c[0]>1:
  print(0)
  sys.exit()
max_key = max(c.keys())


count = 1
for i in range(2,max_key+1):
  a = c.get(i, -1)
  b = c.get(i-1, -1)
  if a == -1 or b == -1:
    print(0)
    sys.exit()
  count = (count * (b**a))%998244353

print(count)

Submission status: Accepted

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

ans = 1
if d[0] == 0 and d.count(0) == 1:
    l = [0 for i in range(10**5+10)]
    for i in range(n):
        l[d[i]] += 1
    
    count = l[0] + l[1]
    for i in range(2,10**5+10):
        if l[i] == 0:
            break
        else:
            ans = ans * l[i-1]**l[i]
   #         print(l[i-1]**l[i],ans)
            count += l[i]
    if count != n:
        ans = 0
    print(ans%998244353)
    
else:
    print(0)

Submission status: Accepted

Solution code:
import collections

input = raw_input
range = xrange
M = 998244353

def main():
    N = int(input())
    Ds = list(map(int, input().split(" ")))
    if Ds[0] != 0:
        return 0

    counter = collections.Counter(Ds)
    depths = counter.keys()
    
    min_depth = min(depths)
    max_depth = max(depths)

    if min_depth != 0:
        #print("test1")
        return 0
    elif counter[0] != 1:
        return 0
    
    if len(depths) != max_depth + 1:
        #print("test2")
        return 0

    out = 1
    for depth in range(1, max_depth+1):
        num = counter[depth]
        if depth >= 2:
            for i in range(num):
                out = out * before_num
                out = out % M
        before_num = num

    return out

out = main()
print(out)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
d = list( map(int, input().split()))
c=Counter(d)
dmax = max(d)
MOD = 998244353

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

if len(c)-1 != dmax:
    print(0)
    exit()

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

ans = 1

for i in range(1,dmax):
    ans *= c[i]**c[i+1]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D.sort()
before_cnt = 1
tmp = 1
cnt = 0
ans = 1
#print(D)
for i in range(1, len(D)):
    #print(ans)
    if (tmp == D[i]):
        cnt += 1
    else:
        if tmp + 1 != D[i]:
            #print("tmp = " + str(tmp))
            print(0)
            exit()
        ans *= before_cnt ** cnt
        tmp = D[i]
        before_cnt = cnt
        cnt = 1

ans *= before_cnt ** cnt
print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
c = [0 for i in range(N)]
if D[0] != 0:
	print(0)
	exit()
for d in D:
	c[d] += 1
MOD = 998244353

if c[0] != 1:
	print(0)
	exit()
flag = True
for i in range(N):
	if not flag and c[i] > 0:
		print(0)
		exit()
	if c[i] == 0:
		flag = False

ans = 1
for i in range(1, N):
	if c[i] == 0:
		print(ans)
		exit()
	t = (c[i-1] ** c[i]) % MOD
	ans = (ans * t) % MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D_list = list(map(int, input().split()))
mod = 998244353
ans = 1
count_list = [0]*(max(D_list) + 1)
if max(D_list) >= N:
    ans = 0
else:
    for i in range(len(D_list)):
        count_list[D_list[i]] += 1
    if count_list[1] == 0:
        ans = 0
    else:
        for i in range(2, len(count_list)):
            if count_list[i] == 0:
                ans = 0
                break
            ans *= count_list[i-1]**count_list[i]

if D_list[0] != 0 or count_list[0] >= 2:
    ans = 0

print(ans%mod)

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
d = list(map(int, input().split()))
a = [0] * (10 ** 5)
if d[0] != 0 or d.count(0) != 1:
  print(0)
  exit()
for i in d:
  a[i] += 1
now = a[1]
if now == 0:
  if n == 1:
    print(1)
    exit()
  else:
    print(0)
    exit()
ans = 1
now_sum = now + 1
for i in a[2:]:
  if not i:
    if n != now_sum:
      ans = 0
    break
  else:
    ans *= pow(now, i, mod)
  now_sum += i
  now = i
print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
d_list = list(map(int, input().split()))
divider = 998244353

if d_list[0] != 0:
  print(0)
else:
  d_sort = sorted(d_list)
  d = 1
  pre_c = 1
  cur_c = 0
  count = 1
  for i in range(1, n):
    if d_sort[i] == d:
      cur_c += 1
    elif d_sort[i] == d + 1:
      count *= pre_c ** cur_c
      count %= divider
      d += 1
      pre_c = cur_c
      cur_c = 1
    else:
      count = 0
      cur_c = 0
      break
  count *= pre_c ** cur_c
  count %= divider
  print(count)

Submission status: Accepted

Solution code:
MOD = 998244353

n = int(input())
D = list(map(int,input().split()))
if D[0]!=0:
    print(0)
    exit()
M = max(D)
L = [0]*(M+1)
for i in range(n):
    L[D[i]] += 1
if L[0]!=1:
    print(0)
else:
    ans = 1
    for i in range(1,M+1):
        ans *= L[i-1]**L[i]%MOD
    print(ans%MOD)

Submission status: Accepted

Solution code:
import math

n = int(input())
a = list(map(int, input().split()))

dist = [0 for i in range(n)]
for i in range(n):
    dist[a[i]] += 1
#print(dist)


if (a[0]!=0):
    print(0)
else:
    zero = 0
    for j in range(n):
        if(a[j]==0):
            zero+=1
    #print(zero)
    if(zero==1):
        ans = 1
        now = 1
        total = 1
        while(total<n and now<=n-1):
            for j in range(dist[now]):
                ans *= dist[now-1]
                #print(ans)
                ans %= 998244353
                total+=1
            now+=1
            
        print(ans)
    else:
        print(0)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = [int(_) for _ in input().split()]
mod = 998244353
C = collections.Counter(D)
if D[0] + 1 == C[0] == 1:
    ans = 1
    for i in range(1, max(C.keys()) + 1):
        ans *= C[i - 1]**C[i]
        ans %= mod
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from itertools import dropwhile

n = int(input())
D = list(map(int, input().split()))
DIV = 998244353

dist = [0]*n

for i in D:
    dist[i] += 1

dist.reverse()
ddist = list(dropwhile(lambda x: x == 0, dist))
ddist.reverse()

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

if ddist[0] != 1 or D[0] != 0:
    ans = 0

print(ans%DIV)

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=sorted(D[1:])
ans=1
count1=1
count2=0
before=1
for i in D:
  if i==count1:
    count2+=1
  elif i==count1+1:
    ans = ans*(before**count2)
    count1+=1
    before=count2
    count2=1
  else:
    print(0)
    sys.exit()
  #print(ans,count1,count2,before)
print((ans*(before**count2))%998244353)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

mod = 998244353

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

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

if len(d) == 1:
    print(1)
    sys.exit(0)

cnt = Counter(d[1:])
keys = sorted(cnt.keys())
for i in range(len(keys)):
    if keys[i] != i+1:
        print(0)
        sys.exit(0)

tree = [cnt[k] for k in sorted(cnt.keys())]

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
s=[0]*n
m=998244353
for i in d:
    s[i]+=1
if d[0]==0 and s[0]==1:
    c=1
    a=1
    for i in range(1,n):
        if s[i]!=0:
            c+=s[i]
            a=(a*pow(s[i-1],s[i],m))%m
        else:
            break
    if c==n:
        print(a%m)
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
def main():
    n = input()
    dd = map(int, raw_input().split())
    count = {}
    for d in dd:
        count[d] = count.get(d, 0) + 1
    if count.get(0, 0) != 1 or dd[0] != 0:
        print 0
        return
    ans = 1
    pre = 0
    for c in sorted(count)[1:]:
        if pre + 1 != c:
            print 0
            return
        ans = ans * pow(count[pre], count[c], 998244353) % 998244353
        pre = c
    print ans


main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    SSSS = 998244353
    D = string_to_int(inputs[0])
    # {distance: numbers}
    nodes = {}
    for i, d in enumerate(D):
        i += 1
        if d not in nodes:
            nodes[d] = [i]
        else:
            nodes[d].append(i)

    if 0 not in nodes:
        return 0

    prev = -1
    prev_num = -1
    count = 0
    for d in sorted(nodes.keys()):
        if d == 0:
            if not (len(nodes[d]) == 1 and nodes[d][0] == 1):
                return 0
            count = 1
            prev_num = 1
            prev = d
            continue
        if abs(d - prev) != 1:
            return 0

        count *= prev_num ** len(nodes[d])
        prev_num = len(nodes[d])
        prev = d
    return count % SSSS


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

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

if D[0] > 0:
    print("0")
    exit()
    
D.pop(0)
list.sort(D)
if D[0] == 0:
    print("0")
    exit()
    
hoge = 0
nyoro = 1
huga = 1
ans = 1
for i in range(N-1):
    if D[i] == hoge:
        nyoro += 1
    elif D[i] == hoge + 1:
        ans *= huga ** nyoro
        hoge += 1
        huga = nyoro
        nyoro = 1
    else:
        print("0")
        exit()
ans *= huga ** nyoro
print(ans % 998244353)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
d = defaultdict(int)
m = 0
for i in a:
    d[i] += 1
    m = max(m,i)
res = 1
tmp = 1
for i in range(m+1):
    if i == 0:
        if d[i] != 1 or a[0] != 0:
            print(0)
            quit()
        continue
    if d[i] == 0:
        res = 0
        break
    if i == 1:
        tmp = d[i]
        continue
    res = (res * tmp ** d[i] )%998244353
    tmp = d[i]
print(res%998244353)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    D = list(map(int, input().split()))
    MOD = 998244353
    for i, d in enumerate(D):
        if (i == 0 and d != 0) or (i > 0 and d == 0):
            print(0)
            exit()
    set_D = list(set(D))
    set_D.sort()
    cnt = 0
    for i in set_D:
        if cnt == i:
            cnt += 1
        else:
            print(0)
            exit()

    A = defaultdict(int)
    for d in D:
        A[d] += 1

    cnt = 1
    pre = 0
    for key, value in A.items():
        if key == 0 or key == 1:
            pre = value
        else:
            cnt *= pre ** value 
            cnt %= MOD
            pre = value
    print(cnt)

    

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

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

ans = 1
m = max(D)
c = collections.Counter(D)

if 0 not in c.keys() or (c[0] != 1 or D[0] != 0):
    print(0)
    exit()

temp = 1
for i in range(1, m+1):
    if i not in c.keys():
        print(0)
        exit()
    ans *= temp**c[i]
    temp = c[i]
    if ans > 998244353:
        ans %= 998244353  

print(ans % 998244353)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = list(map(int, input().split()))
D_C = collections.Counter(D)
D_C = D_C.items()
D_C = sorted(D_C)

#print(D_C)
N = len(D_C)
MOD = 998244353
ans = 1

if (D[0] != 0) or (D_C[0][1] != 1):
  ans = 0
  print(ans % MOD)
  quit()
  
for i in range(N-1):
  ans = ans * (D_C[i][1] ** D_C[i + 1][1])
  if i > 0:
    if D_C[i][0] != x + 1:
      ans = 0
      print(ans)
      quit()
  x = D_C[i][0]

if D_C[N-1][0] != x + 1:
  ans = 0
print(ans % MOD)

Submission status: Accepted

Solution code:
n = int(input())

mod = 998244353

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

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

del d[0]

d.sort()

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

ans = 0
li = []
tmp = d[0]
cnt = 1
#print(d,len(d))

for i in range(len(d)-1):
    #print(i)
    if tmp == d[i+1]:
        cnt += 1
    else:
        li.append(cnt)
        tmp += 1
        if i+1 == len(d)-1:
            cnt = 1
            if d[i+1] != tmp:
                print(0)
                exit()
            break
        else:
            if d[i+1] != tmp:
                print(0)
                exit()
        cnt = 1

li.append(cnt)

ans = 1

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

print(ans)

Submission status: Accepted

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

if(d[0]!=0 or d.count(0)>1):
    print(0)
    sys.exit()

MOD=998244353
max_d=max(d)
c=[0 for _ in range(max_d+1)]
for i in range(n):
    c[d[i]]+=1

ans=1
for i in range(max_d):
    ans*=c[i] ** c[i+1]
print(ans%MOD)

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()
for i in range(1, n):
    if d[i] == 0:
        print(0)
        exit()
d.sort()
for i in range(n-1):
    if d[i+1] - d[i] > 1:
        print(0)
        exit()

c = sorted(Counter(d).items())
ans = 1

for i in range(len(c)-1):
    if c[i][0] == 0: continue
    ans *= c[i][1] ** c[i+1][1]

print(ans % 998244353)

Submission status: Accepted

Solution code:
n = int(input())

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

def f(n,ls):
  if not ls[0] == 0: return 0
  ls = sorted(ls)
  mod = 998244353
  arr = [0]*(ls[-1]+1)
  
  for i in range(n):
    arr[ls[i]] += 1
  if arr[0] >1: return 0
  ans = 1
  for i in range(1,len(arr)):
    
    if arr[i] == 0:
      return 0
    ans *= arr[i-1]**arr[i]
  return ans%mod

print(f(n,ls))

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
d = inl()
#d.insert(0,0)
if d[0]!=0:
    print(0)
    exit()
a = [0]*n
for i in range(n):
    a[d[i]] += 1
if a[0]>1:
    print(0)
    exit()

#ddprint(d)
#ddprint(a)

p = 1
t = -1
for i in range(1,n):
    if a[i]==0:
        t = i
        break
    p = (p * (a[i-1]**a[i])) % R
if t>=0:
  for i in range(t+1,n):
    if a[i]>0:
        print(0)
        exit()
print(p)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(i) for i in input().split()]
a = [0] * n
k = 0
for i in d:
    a[i] += 1
    k=max(k,i)
if d[0] != 0:
    print(0)
elif a[0] != 1:
    print(0)
else:
    j = 1
    for i in range(k):
        j *= a[i] ** a[i + 1]
        j %= 998244353
    print(j)

Submission status: Accepted

Solution code:
n = int(input())
d_list = [int(i) for i in input().split()]
R_max = max(d_list)+1
R = [0] * R_max
ans = 1
if d_list[0] != 0:
  print(0)
  exit()
  
for di in d_list:
  R[di] += 1
  
if R[0] != 1:
  print(0)
  exit()
  
for i in range(1, R_max):
  ans *= R[i-1]**R[i]%998244353
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

num = 998244353

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

if D.count(0) != 1:
    print(0)
    exit()


D_cnt = dict(Counter(D))
D_list = list(D_cnt)
D_list.sort()
ans = 1
# print(D_list == list(range(len(D_list))))
# print(list(range(len(D_list))))
if D_list != list(range(len(D_list))):
    print(0)
    exit()

for i in range(1, len(D_list) - 1):
    n = D_cnt[i]
    m = D_cnt[i + 1]

    ans *= (n ** m)
    ans %= num
print(ans % num)

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline

mod=998244353

def main():
    n,*a=map(int,open(0).read().split())
    if a[0]!=0:
        print(0)
        exit()
    for i in a[1:]:
        if i==0:
            print(0)
            exit()
    
    ans=1
    a=Counter(a)
    for i in range(len(a)-1):
        ans*=pow(a[i],a[i+1],mod)%mod
    print(ans%mod)

    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353
N = int(input())
D = list(map(int,input().split()))
D_max = max(D)
C = [0]*(D_max + 1)
for i in range(len(D)):
    C[D[i]] += 1
tmp = 1
for i in range(len(C)-1):
    tmp = tmp * (C[i]**C[i+1]) % mod
if D[0] != 0 or C[0] > 1:
    tmp = 0
print(tmp)

Submission status: Accepted

Solution code:
import collections
mod=998244353
ans=1
n=int(input())
d=list(map(int,input().split()))
c=collections.Counter(d)
num=[]
for j in range(len(c)):
  num.append(c[j])
if d[0]!=0 or num[0]!=1:
  print(0)
else:
  for i in range(1,len(num)-1):
    ans*=(num[i]**num[i+1])%mod
  print(ans%mod)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = [int(i) for i in input().split()]
mod = 998244353

def solve() :
    c = Counter(D)
            
    if c[0] != 1 or D[0] != 0 :
        return 0
        
    ret = 1
    for i in range(1, max(c) + 1) :        
        ret = ret * pow(c[i-1], c[i], mod) % mod
    
    return ret
        
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
distance_dict = {}
if d[0] != 0:
    print(0)
    exit()
for i in range(1,n):
    if d[i] == 0:
        print(0)
        exit()
    distance_dict[d[i]] = 0

for i in range(1,n):
    distance_dict[d[i]] += 1
pre = 1
ans = 1
for i in range(1,n):
    if i in distance_dict:
      ans *= pre ** distance_dict[i]
      pre = distance_dict[i]
      ans %= mod
      if i != 1 and i - 1 not in distance_dict:
          print(0)
          exit()
print(ans)

Submission status: Accepted

Solution code:
import collections

mod = 998244353

n = int(input())
d = list(map(int, input().split()))
dc = collections.Counter(d).most_common()
dc = sorted(dc)
if d[0] == 0 and dc[0][1] == 1:
    count = 0
    ans = 1
    last = 1
    for i in dc:
        if i[0] == count:
            ans = ans * (last ** i[1]) % mod
            last = i[1]
            count += 1
        else:
            print(0)
            exit()
    print(ans % mod)
else:
    print(0)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(raw_input())
d = map(int, raw_input().split())
count_d = Counter(d)

if count_d[0] != 1 or d[0] != 0:
    print 0
else:
    pre_i = 0
    result = 1
    pre_nodes = 1
    for i, num in count_d.items()[1:]:
        if i != pre_i + 1:
            result = 0
            break
        result *= (pre_nodes ** num)
        pre_i = i
        pre_nodes = num
    print result % 998244353

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))
if D[0] >0:
  print(0)
  exit()
X=[0]*N
for d in D[1:]:
  X[d-1]+=1
ans=1
i=1
while X[i]!=0:
  ans*=X[i-1]**X[i]
  i+=1
while i<N:
  if X[i]!=0:
    ans=0
    break
  i+=1
print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
dic = {}
if d[0]:
    print(0)
else:
    for di in d:
        if di not in dic:
            dic[di] = 0
        dic[di] += 1
    dists = list(dic.keys())
    dists.sort()
    ans = 1
    l = [dic[dist] for dist in dists]
    if l[0] != 1:
        print(0)
    elif dists != list(range(len(dists))):
        print(0)
    else:
        for l1, l2 in zip(l, l[1:]):
            ans = ans * (l1 ** l2) % mod
        print(ans)

Submission status: Accepted

Solution code:
import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations


def li ():
	return list (map (int, sys.stdin.readline ().split ()))


def num ():
	return map (int, sys.stdin.readline ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def lcm ( x, y ):
	gg = find_gcd (x, y)
	return (x * y // gg)



mm = 998244353
def solve ():
	t = 1
	for tt in range (t):
		n=nu()
		a=li()
		if (a [ 0 ] != 0):
			print (0)
			continue
		a.sort()
		if(a[0]!=0):
			print(0)
		else:
			ox=[]
			cc=1
			las=a[0]
			for i in range(1,n):
				if(las==a[i]):
					cc+=1
				else:
					ox.append((las,cc))
					cc=1
					las=a[i]
			ox.append ((las, cc))
			if(ox[0][1]!=1):
				print(0)
				continue
			last=ox[0][1]
			next=ox[0][0]+1
			ans=1
			for i in range(1,len(ox)):
				if(next!=ox[i][0]):
					ans=0
				ans=(ans*pow(last,ox[i][1],mm))%mm
				last=ox[i][1]
				next+=1
			print(ans)










if __name__ == "__main__":
	solve ()

Submission status: Accepted

Solution code:
MOD = 998244353
import collections
N = int(input())
D = list(map(int, input().split()))
mx = max(D)
c = collections.Counter(D)

if D[0] == 0 and c[0] == 1:
    ans = 1
    for i in range(1, mx+1):
        if i not in c:
            ans = 0
            break
        else:
            ans *= (c[i-1] ** c[i]) % MOD
            ans %= MOD
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()
    d = LMIIS()

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

    d.sort()

    a = 1

    c = 0
    old_c = 1
    ans = 1
    for i in range(1, n):
        if d[i] == a:
            c += 1
        elif d[i] == a+1 and c > 0:
            for j in range(c):
                ans = ans * old_c % 998244353
            a += 1
            old_c = c
            c = 1
        else:
            print(0)
            exit()

    if c > 0:
        for j in range(c):
            ans = ans * old_c % 998244353
    print(ans)









if __name__ == '__main__':
    main()