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

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        D = list(map(int, input().split()))

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

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

        cnt = []
        before = 0
        for d in D:
            if d > before + 1:
                print(0)
                exit()
            else:
                if len(cnt) == d - 1:
                    cnt.append(1)
                else:
                    cnt[-1] += 1
                before = d

        ans = 1
        for i, v in enumerate(cnt):
            if i > 0:
                ans *= (cnt[i - 1]) ** v
        print(ans % 998244353)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
import collections
cnt = collections.Counter(D[1:])
if 0 in cnt:
    print(0)
    exit()
maxs = 998244353
res = 1
flag = True
scnt = sorted(cnt.items(), key=lambda x: x[0])
if scnt[0][0] != 1:
    print(0)
else:
    for i in range(1, len(scnt)):
        if scnt[i][0] != scnt[i-1][0] + 1:
            flag = False
            break
        # pre = res
        res = (res * (scnt[i-1][1] ** scnt[i][1])) % maxs
        # print(res)
    print(res) if flag else print(0)

Submission status: Accepted

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

if D[0] != 0:
    print(0)
    exit(0)
    
max_D = max(D)
    
c = [0] * (max_D+1)
for i in range(N):
    c[D[i]] += 1
   
# 他の要素に 0 があるとバツ 
if c[0] > 1:
    print(0)
    exit(0)
   
ans = 1 
for i in range(max_D):
    ans *= c[i] ** c[i+1]
print(ans % 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 n == 1:
    if d[0] == 0:
        print(1)
    else:
        print(0)
    exit()

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


mini = d[0]
maxi = d[-1]
num = 1
cnt = 0
lst = [1]
for i in d[1:]:
    if i == num:
        cnt += 1
    elif i == num+1:
        lst.append(cnt)
        num = i
        cnt = 1
    else:
        print(0)
        exit()

lst.append(cnt)

ans = 1
for i in range(1, len(lst)-1):
    ans = (ans * lst[i]**lst[i+1]) % 998244353

print(ans)

Submission status: Accepted

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

f = 0
if D[0] != 0:
    f = -1
mod = 998244353
L = []

num = 0
cnt = 0
D.sort()
for i in range(N):
    if D[i] == num:
        cnt += 1
    elif D[i] == num+1:
        L.append(cnt)
        cnt = 1
        num += 1
    else:
        f = -1
        break
        
L.append(cnt)
ans = 1
if f == 0:
    if D[0] != 0:
        ans = 0
    if N > 1:
        if D[1] != 1:
            ans = 0
    if ans > 0:
        for i in range(1, len(L)):
            ans *= L[i-1]**L[i]
            ans %= mod
else:
    ans = 0
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

ans = 1
tmp = 1
for i in range(mD+1):
    if not(i in c.keys()):
        ans = 0
        break
    elif i == 0:
        if c[0] > 1:
            ans = 0
            break
    elif i == 1:
        tmp = c[i]
    else:
        ans = (ans * tmp**c[i])%MOD
        tmp = c[i]

if D[0] != 0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
D = groupby(sorted(D))
t = 998244353

ans = 1
pre = 0
cur = 0
for i, d in D:
    if i != cur:
        print(0)
        exit()
    else:
        cur += 1
    l = len(list(d))
    if i == 0 and l > 1:
        print(0)
        exit()
    if i <= 1:
        pre = l
        continue
    ans = ans * (pre**l)
    pre = l

print(ans % t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    l = {}
    o = list(map(int, input().split()))
    if o[0] != 0:
        print(0)
        exit()
    for i in o:
        if i in l:
            l[i] += 1
        else:
            l[i] = 1
    
    count = 1
    m = max(l)
    if 0 not in l:
        print(0)
        exit()
    if l[0] >= 2:
        print(0)
        exit()
    
    for i in range(1,m+1):
        if i in l:
            count *= l[i-1] ** l[i] % 998244353
        else:
            print(0)
            exit()
    
    print(count%998244353)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
Ds = list(map(int, input().split()))
if Ds[0] != 0:
  print(0)
  exit()
Ns = [0]*N
for D in Ds:
  Ns[D] += 1
#print(Ns)
if Ns[0] != 1:
  print(0)
  exit()
r = 1
p = 1
for n in Ns:
  #r = r*(p**n)%998244353
  for i in range(n):
    r = r*p%998244353
  p = n
print(r)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
num=[0 for i in range(n)]
ans=1
flag=0
for i in d:
  num[i]+=1
if d[0]>=1:
  ans=0
else:
  for i in range(1,n-1):
      ans*=num[i]**num[i+1]
      while ans>998244353:
        ans=ans%998244353
for i in range(1,n):
  if d[i]==0 and ans>0:
    ans=0
#  if d[i]==0:
#    flag=1
#  if flag==1 and d[i]>0:
#    ans=0
print(ans)

Submission status: Accepted

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

cnt = [0]*n

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

for e in d:
    cnt[e] += 1

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

res = 1
for i in range(1,n):
    if cnt[i] != 0:
        if cnt[i-1] == 0:
            print(0)
            exit()
        res = res*pow(cnt[i-1],cnt[i],mod)%mod

print(res%mod)

Submission status: Accepted

Solution code:
import heapq
mod = 998244353
n = int(input())
d = list(map(int, input().split()))
q = []
if d[0] != 0:
  print(0)
else:
  for x in d[1:]:
    heapq.heappush(q, x)
  prev = 0
  x = 0
  y = 1
  ans = 1
  for i in range(n-1):
    a = heapq.heappop(q)
    if a == 0:
      print(0)
      break
    elif a == prev:
      x += 1
    elif a == prev + 1:
      x += 1
      ans = ans * (y ** x) % mod
      y = x
      x = 0
    else:
      print(0)
      break
    prev = a
  else:
    x += 1
    ans = ans * (y ** x) % mod
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n=int(input())
	D=list(map(int,input().split()))
	
	
	if D[0]!=0:
		print(0)
		exit(0)
	
	if len(D)==1:
		print(1)
		exit(0)
		
		
	D.sort()
	
	if D[1]!=1:
		print(0)
		exit(0)
	
	ans=1
	
	li=[0]*n
	
	for i in range(n):
		li[D[i]]+=1
	
	for i in range(1,n):
		ans*=li[D[i]-1]
		ans%=998244353
	
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

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

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

 #1からmaxdまでの距離について、それぞれ何個のdが該当するかメモした配列
maxd=max(d)
kyori=[0]*(maxd+1)

#計算量減らし、、
for i in d:
  kyori[i]+=1

#1個目以外で距離0のやつある場合は停止。
if kyori[0]!=1:
  print(0)
  exit()

ans=1
for i in range(1,maxd):
  temp=kyori[i]**kyori[i+1]
  ans*=temp%998244353
  ans=ans%998244353
print(ans)

Submission status: Accepted

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

ans = 1
# 距離:頂点に対応する辞書
if D[0] != 0:
    ans = 0
distance_dict = {0:1}
for i in D[1:]:
    if not i in distance_dict:
        distance_dict[i] = 1
    else:
        distance_dict[i] += 1

#dist_list = list((distance_dict.keys())) # 0~N-1 一つでもとんでったらアウト。距離がない
#print(distance_dict)

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

for i in range(1,max(distance_dict.keys())+1):
    if not i in distance_dict: # 一つでもとんでったらアウト。距離がない。連結できない
        ans = 0
        print(0)
        exit()

    elif i != 0:
        ans *= (distance_dict[i-1]**distance_dict[i]) # どこにつながるかの候補とつながる点の数
print(ans%BIGNUM)

Submission status: Accepted

Solution code:
# B
from collections import Counter
mod = 998244353
n = int(input())
dli = list(map(int, input().split()))
for ind in range(len(dli)):
    if (ind == 0):
        if (dli[ind] != 0):
            print(0)
            exit()
    else:
        if (dli[ind] == 0):
            print(0)
            exit()

count = Counter(dli)
# 木である条件
for ind, key in enumerate(count.keys()):
    if ind != key:
        print(0)
        exit()

sort = sorted(count.items(), key=lambda x:x[0])

tmp = []
for ind in range(len(sort)-1):
    mae = sort[ind][1]
    next = sort[ind+1][1]

    tmp.append(int(mae**next))

total = 1
for t in tmp:
    total *= t
print(total%mod)

Submission status: Accepted

Solution code:
N = int(input())
Dn = list(map(int,input().split(' ')))
#Dn.sort()
previous_num = 0
previous_cnt = 1
current_num = 0
sum_num = 1
flag = False
output_list = [0]* N
max_num = 0
if Dn[0] == 0:
    output_list[0] = 1
    for i in range(1,N):
        max_num = max(max_num,Dn[i]) 
        output_list[Dn[i]] +=1


    '''
    for i in range(1,N):
        if Dn[i] == previous_num + 1:
            current_num += 1
        elif Dn[i] == previous_num + 2:
            if previous_num > 0:
                sum_num = sum_num * (previous_cnt**current_num)
            previous_cnt = current_num
            previous_num += 1
            current_num = 1
        else:
            flag = True
            break
        if i == N-1:
            if previous_num > 0:
                sum_num = sum_num * (previous_cnt**current_num)
    if flag:
        print(0)
    else:
        print(sum_num%998244353)
    '''
    if output_list[0] !=1:
        print(0)
    else:
        for i in range(2,max_num+1):
            sum_num = sum_num * (output_list[i-1]**output_list[i])
        print(sum_num%998244353)
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 998244353

def beki(x, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    return beki(x * x % MOD, n // 2) % MOD
  else:
    return x * beki(x, n - 1) % MOD


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

ans = 1
cnt = 1
precnt = 1

if Orig[0] != 0:
    ans = 0
if N >= 2 and D[1] == 0:
    ans = 0

for i in range(N-1):
    if D[i] == D[i+1]:
        cnt += 1

    elif D[i] + 1 != D[i+1]:
        ans = 0
        break

    else:
        ans *= beki(precnt, cnt)
        ans %= MOD
        precnt = cnt
        cnt = 1
        if (i == N-1):
            break
else:
    ans *= beki(precnt, cnt)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
p=998244353
n=int(input())

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

kanou=True

if(a[0]!=0):
    print(0)
    kanou=False

a.sort()
#print(a)


cnt=[0]*n

if(kanou):
    if(n==1):
        if(a[0]==0):
            print(1)
        else:
            print(0)
        kanou=False
    elif(a[0]!=0 or a[1]==0):
        print(0)
        kanou=False



if(kanou):
    cnt[0]=1
    temp=0
    for c in a:
        if(c==0):
            continue
        if(c==temp):
            cnt[c]+=1
        elif(c==temp+1):
            cnt[c]+=1
            temp+=1
        else:
            kanou=False
            print(0)
            break

#print(cnt)
ans=1
if(kanou):
    for i in range(1,n):
        if(cnt[i]==0):
            break
        ans*=cnt[i-1]**cnt[i]
        ans%=p

    print(ans)

Submission status: Accepted

Solution code:
def listConvert(baseList):
  maxNum = max(baseList)
  newList = [0] * (maxNum + 1)
  for a in baseList:
    newList[a] += 1
  return newList

def mainFunc(baseList):
  if baseList[0] != 0:
    return 0

  newList = listConvert(baseList)
  if newList[0] > 1:
    return 0
  if newList.count(0) > 0:
    return 0

  result = 1
  preA = 1
  mod = 998244353
  for a in newList:
    result = (result * pow(preA, a)) % mod
    preA = a
  return result

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

print(mainFunc(baseList))

Submission status: Accepted

Solution code:
import collections
n = int(input())
d = list(map(int, input().split()))
fl = False
if d[0] != 0:
  fl = True
  print(0)
else:
  del d[0]
  c = collections.Counter(d)
  ll = len(c)
  ans = 1
  for i in range(1, ll+1):
    if c[i] == 0:
      print(0)
      fl = True
      break
    else:
      if i != 1:
        ans *= c[i-1]**c[i]

if not fl:
  print(ans%998244353)

Submission status: Accepted

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

def calc():
    if D[0] != 0:
        return 0
    if sum(D) < N-1:
        return 0
    
    c = Counter(D)
    ret = 1
    tmpkey = 0
    tmpvalue = 0
    for key in sorted(c.keys()):
        if key - tmpkey >= 2:
            return 0
        if key == 0:
            if c[key] >= 2:
                return 0
        else:
            ret *= (tmpvalue ** c[key]) % MOD
            ret %= MOD
        tmpkey = key
        tmpvalue = c[key]
    return ret

print(calc())

Submission status: Accepted

Solution code:
valid = True
n = int(input())
ds = [int(i) for i in input().split()]
if(ds[0]!=0):
    valid = False
    print(0)
ds.sort()
count = []
c = 1
for i in range(len(ds)-1):
    if(not i==0 and ds[i]==0):
        valid = False
        print(0)
        break
    if(ds[i]==ds[i+1]):
        c += 1
    elif(ds[i]==ds[i+1]-1):
        count.append(c)
        c = 1
    else:
        valid = False
        print(0)
        break
count.append(c)

s = 1
for i in range(len(count)-1):
    s *= count[i]**count[i+1]

if(valid):
    print(int(s)%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    arr = list(map(int,input().split()))
    if arr[0] != 0:
        print(0)
        return
    
    mod = 998244353
    dist = {}
    arr1 = []
    for i in arr:
        if i not in dist.keys():
            dist[i] = 1
            arr1.append(i)
        else:
            dist[i] += 1

    if dist[0] > 1:
        print(0)
        return

    arr1.sort()
    ways = 1
    for i in range(1,len(arr1)):
        ways *= pow(dist[arr1[i-1]],dist[arr1[i]],mod)
        ways = ways%mod
        if arr1[i] - arr1[i-1] != 1:
            print(0)
            return

    print(ways)
         

main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(10**5)]
MOD = 998244353

max_B = -1
ans = 1

for i in range(1, len(A)):
    if A[i]==0:
        ans = 0
    else:
        B[A[i]-1] += 1
    if A[i] > max_B:
        max_B = A[i]

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

for i in range(1, max_B):    
    if B[i] == 0:
        ans = 0 
        break
    else:
        ans = (ans * (B[i-1] ** B[i])%MOD)%MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

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

stage = [0]*n
maxstage = 0
for di in d:
    stage[di] +=1
    maxstage = max(maxstage, di)

if stage[0] != 1:
    print(0)
elif d[0] != 0:
    print(0)
else:
    cnt = 1
    for i in range(1,maxstage+1):
        cnt = (cnt*stage[i-1]**stage[i])%MOD
           
    print(cnt)

Submission status: Accepted

Solution code:
INFTY = 998244353
N = int(input())
D = list(map(int,input().split()))
C = {}
dmax = 0
for i in range(N):
    d = D[i]
    dmax = max(dmax,d)
    if d not in C:
        C[d] = 0
    C[d] += 1
if D[0]!=0 or C[0]!=1:
    flag = 1
else:
    flag = 0
    for i in range(dmax+1):
        if i not in C:
            cnt = 0
            flag = 1
            break
if flag==1:
    cnt = 0
else:
    cnt = 1
    for i in range(1,dmax):
        cnt = (cnt*(C[i]**C[i+1]))%INFTY
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
mod=998244353
N=int(input())
D=list(map(int,input().split()))
if D[0]!=0:
  print(0)
else:
  tmp=Counter(D)
  if tmp[0]!=1:
    print(0)
  else:
    ans=1
    for i in tmp.keys():
      if i==0 or i==1:
        continue
      ans*=tmp[i-1]**tmp[i]
      ans%=mod
    print(ans)

Submission status: Accepted

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

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

length = 1
length_list = []
count = 0
for i in range(len(D)):
    if length == D[i]:
        count += 1
    else:
        if length+1 != D[i]:
            print(0)
            exit()
        else:
            length += 1
            length_list.append(count)
            count = 1
length_list.append(count)
        
ans = 1
for i in range(len(length_list)-1):
    ans *= length_list[i] ** length_list[i+1]
    ans %= 998244353


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
d = { }
for i in range(N+1):
    d[i] = 0
for i in range(N):
    x = D[i]
    d[x] += 1
p = 0
if D[0] == 0:
    p = 1
q = 0
if d[0] == 1:
    q = 1
M = max(D)
r = 1
e = 998244353
for i in range(1,M):
    x = d[i]
    y = d[i+1]
    r = r*(x**y) % e
ans = p*q*r
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))
dp=[0]
x,r=0,1
m=998244353
if D[0]!=0:
    r=0
D.sort()
for d in D:
    if d==x:
        dp[x]+=1
    elif d==x+1:
        dp.append(1)
        x+=1
    else:
        r=0
    r=(r*dp[x-1])%m
print(r%m if dp[0]==1 else 0)

Submission status: Accepted

Solution code:
import collections
import sys


def solve():
    input = sys.stdin.readline
    mod = 998244353
    n = int(input().rstrip('\n'))
    d = list(map(int, input().rstrip('\n').split()))
    mn = 0
    dic = collections.defaultdict(list)
    for i in range(n):
        dic[d[i]] += [i+1]
        mn = max(mn, d[i])
    if len(dic[0]) == 1 and d[0] == 0:
        ln = 1
        t = 1
        for i in range(1, mn+1):
            if len(dic[i]) != 0:
                t *= ln ** len(dic[i])
                t %= mod
                ln = len(dic[i])
            else:
                print(0)
                exit()
        print(t)
    else:
        print(0)
        exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- Coding: utf-8 -*-

import sys
from collections import Counter


input = sys.stdin.readline
MOD = 998244353


def main():
    N = int(input())
    D = [int(i) for i in input().split()]
    c = Counter(D)
    k = list(c.keys())
    k.sort()
    if D[0] != 0 or c[0] != 1:
        print(0)
        sys.exit(0)

    ans = 1
    for i, n in enumerate(k):
        if i != n:
            print(0)
            sys.exit(0)
        if n == 0:
            continue
        ans *= c[n-1]**c[n]

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

import sys
big=998244353

n = int(input())
d = list(map(int, input().split()))
d_sort = sorted(d)


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

for i in range(n-1):
  if d_sort[i+1]-d_sort[i]>1:
    print(0)
    sys.exit(0)


def cho(node0,node1):
  #tmp0 = 2**node0-1
  #tmp0 = tmp0%big
  #tmp1 = 2**(node1*(node1-1)/2)
  #tmp1 = tmp1%big
  return (node0**node1) % big


c = collections.Counter(d)

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

count=1
for i in range(max(d)):
  count *= cho(c[i], c[i+1])
  #print("i=", i, c[i], c[i+1], cho(c[i], c[i+1]))
  count=count%big

print(count)

Submission status: Accepted

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

if e[0] != 0:
  ans = 0
else:
  ce = Counter(e)
  sce = sorted(ce.items())
  # keyの数が連番であることを確認
  if sce[-1][0] != len(sce) - 1 or sce[0][1] != 1:
    ans = 0
  else:
    ans = 1
    pre = 1
    for i, j in sce:
      if pre != 1:
        ans = (ans * (pre ** j)) % 998244353
      pre = j
      
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

_n = int(input())
_dlist = list(map(int, input().split()))


def chker(n, dlist):
    if dlist[0] != 0:
        print(0)
        return

    ds = dlist[1:]
    ds.sort()
    cntlist = [0] * n
    if ds[0] != 1:
        print(0)
        return

    cntlist[ds[0]] = 1
    for i in range(1, n - 1):
        if ds[i] <= ds[i - 1] + 1:
            cntlist[ds[i]] += 1
        else:
            print(0)
            return

    ans = 1
    for i in range(2, n):
        ans = (ans * cntlist[i - 1] ** cntlist[i]) % 998244353

    print(ans)


chker(_n, _dlist)

Submission status: Accepted

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

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

D.sort()

chouten = {}
for i in D:
    if i not in chouten:
        chouten[i] = 0
    chouten[i] += 1

# print(chouten)

if 0 not in chouten or chouten[0] != 1:
    print(0)
    exit()

kosuu = 1
# for k, v in chouten.items():
#     if k == 0:
#         continue
#     if k == 1:
#     kosuu = kosuu**v

for i in range(len(chouten)):
    if i not in chouten:
        print(0)
        exit()
    if i == 0:
        continue
    elif i == 1:
        continue
        kosuu = chouten[i]
    else:
        kosuu *= chouten[i - 1]**chouten[i]
        kosuu = kosuu % 998244353

print(kosuu)

Submission status: Accepted

Solution code:
n= int(input())

dlist = list(map(int,input().split()))
lendlist = len(dlist)
ans = -1
dictdist = {}

for i in range(100001):
    dictdist[i] = 0

for i in range(lendlist):
    if i==0:
        if dlist[i]!=0:
            ans = 0
            
    elif i!=0:
        if dlist[i]==0:
            ans = 0
        else:
            dictdist[dlist[i]] += 1
                
if ans != 0:
    temp = 1
    for k,v in dictdist.items():
        if k != 1:
            for _ in range(v):
                temp *= dictdist[k-1]
                temp %= 998244353
                #print(temp)
    ans = temp
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter 

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

answer = 1
prev = 1
count = Counter(D)
for i in range(max(count.keys()) + 1):
    if D[0] != 0 or (i == 0 and count[i] != 1):
        answer = 0
        break
    if i not in count:
        answer = 0
        break
    answer *= prev ** count[i]
    prev = count[i]
print(answer % 998244353)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

N = int(input().strip())
D = [int(x) for x in input().strip().split()]
maxD = max(D)
C = [0] * (maxD + 1)
for d in D:
    C[d] += 1
ans = 1
c_ = 1
if C[0] != 1 or D[0] != 0:
    ans = 0
else:
    for i, c in enumerate(C[1:], start=1):
        ans *= c_ ** c
        ans %= 998244353
        c_ = c

print(ans)

Submission status: Accepted

Solution code:
import collections

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

if d_list[0] != 0:
  print(0)
elif 0 in d_list[1:]:
  print(0)
else:
  d_count_dict = collections.Counter(d_list)
  start_num = -1
  answer = 1
  last = 1
  for num, cnt in d_count_dict.items():
    if num != start_num + 1:
      answer = 0
    else:
      answer *= ((last ** cnt)%998244353)
      last = cnt
      start_num = num
  print(answer % 998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
ans = 1
count1 = 1
count = 0
now = 0
mod = 998244353
if d[0] != 0:
    print(0)
else:
    d.sort()
    for i in range(1,n):
        if d[i] == now+1:
            count += 1
        else:
            if count == 0 or d[i] == 0:
                ans = 0
                break
            elif d[i] > now + 2:
                ans = 0
                break
            else:
                p = 1
                for j in range(count):
                    p *= count1
                    p %= mod
                ans *= p
                ans %= mod
                count1 = count
                count = 1
                now += 1
        #print(count,count1,now)
    p = 1
    for i in range(count):
        p *= count1
        p %= mod
    ans *= p
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
D = list(map(int,input().split()))
mod = 998244353
if D[0]!= 0:
  print(0)
else:
  D.sort()
  if D[0]==0 and D[1]==0:
    print(0)
  elif D[0] ==0 and D[1] != 1:
    print(0)
  else:
      D += [max(D)+1]
      ans = 1
      before = 1
      now = 1
      ok =True
      for i in range(1,n):
          if D[i]==D[i+1]:
              now +=1
          else:
            if D[i+1] == D[i]+1:
                ans *= ((before%mod)**now)%mod
                before = now
                now = 1
                ans = ans%mod
            else:
              print(0)
              ok = False
              break
      if ok:
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(i) for i in input().split(" ")]
if d[0]!=0:
    print(0)
else:
    te = [1] + [0 for i in range(max(d))]
    co = [0 for i in range(max(d)+1)]
    for i in d:
        co[i] += 1
    if 0 in co[1:]:
        print(0)
    elif co[0] != 1:
        print(0)
    elif len(co)==2:
        print(1)
    else:
        for i in range(1,len(co)):
            te[i] = te[i-1]*(co[i-1]**co[i]) % 998244353

        print(te[-1])

Submission status: Accepted

Solution code:
N = int(input())
Ds  = list(map(int, input().split()))
if Ds[0] != 0:
    print(0)
    exit()
Ds.sort()

mod = 998244353

from collections import defaultdict
d = defaultdict(int)

d_max = Ds[-1]
for D in Ds:
    d[D] += 1

ans = 1

for i in range(1,d_max+1):
    ans *= pow(d[i-1],d[i],mod)%mod
if d[0] > 1:
    print(0)
else:
    print(ans%mod)

Submission status: Accepted

Solution code:
import sys


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

if d[0] != 0:
    print(0)
    sys.exit()
d.sort()
ans = 1
key = 1
value = 1
for i in range(1, n):
    if i == 1 and d[i] != 1:
        print(0)
        sys.exit()
    else:
        pass
    if d[i] == d[i-1]:
        key += 1
    else:
        if d[i] == d[i-1] + 1:
            if d[i-1] == 1:
                value = key
                key = 1
            else:
                ans *= pow(value, key)%998244353
                value = key
                key = 1
        else:
            print(0)
            sys.exit()
t = pow(value, key)
ans = ans*t%998244353
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 998244353
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

N = int(input())
D = LI()

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

if 0 in D[1:]:
    print(0)
    sys.exit()


D.sort()
c = collections.Counter(D)
ans = 1
parents = 1
before = -1
for key in c.keys():
    if before + 1 != key:
        print(0)
        sys.exit()
    ans *= parents**c[key]
    ans = ans % mod
    parents = c[key]
    before = key

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def read():
    N = int(input().strip())
    D = list(map(int, input().strip().split()))
    return N, D

def argsort(x):
    pairs = [(i, x[i]) for i in range(len(x))]
    pairs.sort(key=lambda a: a[1])
    return [a[0] for a in pairs]


def solve(N, D, P=998244353):
    D = [-1] + D
    count = Counter(D)
    count_max = max(count.keys())

    if not(D[1] == 0 and count[0] == 1):
        return 0

    result = 1
    for i in range(1, count_max + 1):
        if count[i] == 0:
            return 0
        n_childs = count[i]
        n_parents = count[i-1]
        ptn = n_parents ** n_childs
        result *= ptn
        result %= P
    return result

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

if 0 in D[1:] or D[0] != 0:
    print(0)
    exit(0)
else:
    num = [0]*max(D)
    for i in range(1, N):
        if D[i] > 0:
            num[D[i]-1] += 1

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

    print(ans % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
d = list(map(int, input().split()))

cnt = dict()
for k in d:
    if k in cnt:
        cnt[k] += 1
    else:
        cnt[k] = 1

mod = 998244353

keys = cnt.keys()
pre = -1
rst = 1

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


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


for k in sorted(keys):
    if (pre + 1) != k:
        rst = 0
        break
    pre = k

    if k == 0:
        continue

    rst = (rst * (cnt[k-1] ** cnt[k])) % mod
    
print(rst)