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
from collections import defaultdict

N = int(input())
tmp = [int(i) for i in input().split()]
if tmp[0] != 0:
    print(0)
    exit()
D = defaultdict(int)
for i in tmp:
    D[int(i)] += 1
D_len = max(tmp)

MOD = 998244353

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

answer = 1
for i in range(1,D_len+1):
    if D[i] == 0:
        answer = 0
        break
    tmp = 1
    for _ in range(D[i]):
        tmp = (tmp * D[i-1]) % MOD
    answer = (answer * tmp) % MOD

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A)
D = {}
for i in range(N):
  if A[i] in D:
    D[A[i]] += 1
  else:
    D[A[i]] = 1
sorted(D)
S = 1
if A[0] == 0 and D[0] == 1:
  for i in D:
    if i != M:
      if i + 1 not in D:
        S = 0
        break
      else:
        S *= (D[i] ** D[i+1]) % 998244353
        S %= 998244353
else:
  S = 0
print(S % 998244353)

Submission status: Accepted

Solution code:
N=int(input())
D=[int(i) for i in input().split()]
ans=1
mod=998244353
M=max(D)+1
X=[0 for i in range(M)]
for i in range(N):
    X[D[i]]+=1
if X[0]!=1:
    print(0)
    exit()
if D[0]!=0:
    print(0)
    exit()
if N==1:
    print(1)
    exit()
if N==2:
    if D[0]==0 and D[1]==1:
        print(1)
    else:
        print(0)
    exit()
#print(X)
for i in range(1,M-1):
    #print(X[i],X[i+1])
    ans=ans*pow(X[i],X[i+1],mod)
    ans%=mod
print(ans)

Submission status: Accepted

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

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

a.sort()
b = set(a[1:])
if 0 in b:
    print(0)
    exit()

num = max(b) - min(b) + 1
if num != len(b):
    print(0)
    exit()

count_pre = 1
count_now = 1
ans = 1
for i in range(1, n-1):
    if a[i] == a[i+1]:
        count_now += 1
    else:
        ans *= (count_pre ** count_now)
        ans %= 998244353
        count_pre = count_now
        count_now = 1
ans *= (count_pre ** count_now)
ans %= 998244353

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
d = list(map(int,input().split()))
l = Counter(d)
if d[0] != 0 or l[0] != 1:
  print(0)
else:
  a = 1
  for i in range(1,max(l)+1):
    a = (a*pow(l[i-1],l[i],998244353)) % 998244353
  print(a)

Submission status: Accepted

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

count = [0]*(max(D)+1)
ans = 1

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

if count[0] != 1 or D[0] != 0:
  print(0)
  exit()
 
for i in range(1,max(D)+1):
    ans *= count[i-1]**count[i]
    ans %= 998244353
print(ans)

Submission status: Accepted

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

MOD = 998244353

from collections import defaultdict

count = defaultdict(int)

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

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

tmp = 0
ans = 0
check = 0
for i in range(N):
    if i == 0:
        if count[i] == 1:
            ans = 1
            tmp = 1
            check += 1
        else:
            print (0)
            exit()
    else:
        ans *= pow(tmp, count[i], MOD)
        tmp = count[i]
        check += count[i]
    # print (i)
    ans %= MOD

    if check == N:
        break
    
    if count[i] == 0:
        print (0)
        exit()

print (ans % MOD)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0:print(0)
else:
  a.sort()
  mod=998244353
  if n==1:print(1)
  elif a[1]==0:print(0)
  else:
    li=[]
    ans=1
    a+=[a[-1]+1]
    check=0
    for i in range(1,n):
      if abs(a[i]-a[i+1])>=2:print(0);exit()
      if a[i]!=a[i+1]:
        if li==[]:
          li.append(i)
          check=i
        else:
          li.append(i-check)
          check=i
    for i in range(len(li)-1):
      ans=ans*(li[i]**li[i+1])
      ans%=mod
    print(ans%mod)

Submission status: Accepted

Solution code:
import cmath
import sys

INF=10**18
MOD=998244353
MAX=10**5+7

def main():
    N=int(input())
    D=list(map(int, input().split()))
    cnt=[0]*(N+1)

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

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

    ans=1
    for  i in range(1, max(D)+1):
        ans=ans*pow(cnt[i-1], cnt[i], MOD)%MOD
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import cmath
import sys

INF=10**18
MOD=998244353
MAX=10**5+7

def main():
    N=int(input())
    D=list(map(int, input().split()))
    cnt=[0]*(N+1)

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

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

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

    ans=1
    for  i in range(1, max(D)+1):
        ans=ans*pow(cnt[i-1], cnt[i], MOD)%MOD
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

fq = [0] * (N + 10)

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

if not (D[0] == 0 and fq[0] == 1):
    print(0)
    exit()

ans = 1
for i in range(2, N+1):
    ans = (ans * (fq[i-1] ** fq[i] % 998244353)) % 998244353

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353

N = int(input())
D = list(map(int, input().split()))
M = [0 for _ in range(N)]

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

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

res = 1
for i in range(1, N):
    res = (res * M[D[i] - 1]) % MOD

print(res)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(i) for i in input().split()]
#存在しないとき
if d[0] != 0:
    print(0)
    exit()
d0 = sorted(d)
for i in range(n-1):
    if d0[i+1] -d0[i] > 1:
        print(0)
        exit()
if d0[1] == 0:
    print(0)
    exit()
#############
dmax = d0[n-1]
if dmax == 1:
    print(1)
    exit()
l1 = 0
k = 1
for i in range(1,n):  
    if d0[i] == 1:
        l1 += 1
        k += 1
    else:
        break
l = [1,l1]
#print(l1)
ans = 1
for i in range(2,dmax+1):
    tmp = 0
    for j in range(k,n):
        if d0[j] == i:
            tmp += 1
            k += 1
        else:
            break
    #print(tmp)
    l.append(tmp)
    ans = ans * (l[i-1] ** l[i]) % 998244353
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
a=lists.copy()
anslist=[0 for i in range(n+1)]
for j in lists:
    anslist[j]+=1
if anslist[0]!=1:
    print(0)
else:
    ans=1
    for j in range(n):
            for k in range(anslist[j+1]):
                ans=anslist[j]*ans
                ans=ans%(998244353)
    if a[0]!=0:
      print(0)
    else:
      print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

def count_tree(d):
    n = max(int(i) for i in d)
    cnt = 1
    if d[0] != "0":
        return 0
    dd = Counter(d)
    if dd["0"] != 1:
        return 0
    for i in range(1, n):
        if dd[str(i + 1)] > 0 and dd[str(i)] < 1:
            return 0
        else:
            cnt *= pow(dd[str(i)], dd[str(i + 1)], 998244353)
    return cnt % 998244353

input()
print(count_tree(input().split()))

Submission status: Accepted

Solution code:
import math

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

for i in range(N):
    if D.get(T[i],None)==None:
        D[T[i]]=1
    else:
        D[T[i]]+=1

Max=max(D)
Min=min(D)
Len=len(D)
Item=sorted((D.items()))
if(Item[0][1]!=1):
        print("0")
        exit()
for i in range(Len):
    if(Item[i][0]!=i):
        print("0")
        exit()
ans=1
for i in range(1,Len):
    ans = (ans * (Item[i-1][1]**Item[i][1])) % 998244353
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    D = inputList()
    
    if D[0] != 0:
        print(0)
        sys.exit()
        
    if N == 1:
        print(1)
        sys.exit()
        
    D.sort()
    
    if D[1] != 1:
        print(0)
        sys.exit()
        
    ck = 0
    dict_tmp = {}
    for i,val in enumerate(D):
        if ck == val:
            pass
        elif ck+1 == val:
            ck += 1
        else:
            print(0)
            sys.exit()
            
        if val in dict_tmp:
            dict_tmp[val] += 1
        else:
            dict_tmp[val] = 1
            
    ans = 1
    for k,v in dict_tmp.items():
        if k == 0 or k == 1:
            pass
        else:
            tmp = dict_tmp[k-1]
            for i in range(v):
                ans *= tmp
                ans = ans % 998244353
                
    print(ans)
            
    
    
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# 最初dは与えられる距離だと思ってて「サンプルケース1は3じゃね？」とか思ってて2時間経過した
# 落ち着いて読んだら最小の辺の数だった

from collections import Counter

n = int(input())
arr = list(map(int, input().split()))
if arr[0] != 0:
    print(0)
    exit()
arr = sorted(list(Counter(arr).items()), key=lambda x: x[0])
if arr[0][1] > 1:
    print(0)
    exit()

mod = 998244353
ans = 1
tmp = 1
for i in range(1, len(arr)):
    if arr[i][0] != i:
        print(0)
        exit()
    ans *= pow(tmp, arr[i][1])
    ans %= mod
    tmp = arr[i][1]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = [int(x) for x in input().split()]
res = [0]*(max(D)+1)
for n in range(N):
    res[D[n]] += 1
if D[0] != 0 or res[0] != 1:
  print(0)
else:
  k = 1
  for n in range(1,max(D)+1):
    k *= pow(res[n-1],res[n],998244353)
  print(k%998244353)

Submission status: Accepted

Solution code:
from sys import exit

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

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

c = {}
for i in D:
    if i in c:
        c[i] += 1
    else:
        c[i] = 1

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

result = 1
for i in range(1, N + 1):
    if i not in c:
        if max(D) == i - 1:
            break
        else:
            print(0)
            exit()
    result = result * (c[i - 1] ** c[i]) % 998244353
print(result)

Submission status: Accepted

Solution code:
from collections import Counter
mod = 998244353

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

else:
    D = Counter(d)
    if D[0] >= 2:
        print(0)
        exit()
    else:

        ans = 1
        c = 1
        for i in range(max(D.keys())+1):
            ans *= c ** D[i]
            ans %= mod
            c = D[i]

        print(ans)

Submission status: Accepted

Solution code:
def main():

    N = input()
    D = list(map(int,input().split()))
    M = max(D)
    countlist=[0] * (M + 1)
    ans=1

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

    if countlist[0]!=1 :
        ans = 0
    else :
        if D[0]!=0 :
            ans = 0
        else:
            for i in range(2,M+1):
                ans = (ans * (countlist[i-1]**countlist[i])) % 998244353

    print(ans) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    N = input()
    D = list(map(int,input().split()))
    M = max(D)
    countlist=[0] * (M + 1)
    ans=1

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

    if countlist[0]!=1 :
        ans = 0
    else :
        if D[0]!=0 :
            ans = 0
        else:
            for i in range(2,M+1):
                ans *= (countlist[i-1]**countlist[i])

    print(ans % 998244353) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    N = input()
    D = list(map(int,input().split()))
    M = max(D)
    countlist=[0] * (M + 1)
    ans=1

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

    if countlist[0]!=1 :
        ans = 0
    else :
        if D[0]!=0 :
            ans = 0
        else:
            for i in range(2,M+1):
                ans *= (countlist[i-1]**countlist[i])
                ans = ans  % 998244353

    print(ans) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    N = input()
    D = list(map(int,input().split()))
    M = max(D)
    countlist=[0] * (M + 1)
    ans=1

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

    if countlist[0]!=1 :
        ans = 0
    else :
        if D[0]!=0 :
            ans = 0
        else:
            for i in range(2,M+1):
                ans = ans * (countlist[i-1]**countlist[i]) % 998244353

    print(ans) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    N = input()
    D = list(map(int,input().split()))
    M = max(D)
    countlist=[0] * (M + 1)
    ans=1

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

    if countlist[0]!=1 :
        ans = 0
    else :
        if D[0]!=0 :
            ans = 0
        else:
            for i in range(2,M+1):
                ans *= countlist[i-1]**countlist[i]

    print(ans%998244353) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=[0] * (M + 1)
ans=1

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

if countlist[0]!=1 :
    ans = 0
else :
    if D[0]!=0 :
        ans = 0
    else:
        for i in range(2,M+1):
            ans *= countlist[i-1]**countlist[i]

print(ans%998244353)

Submission status: Accepted

Solution code:

import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=[0] * (M + 1)
ans=1

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

if countlist[0]!=1 :
    print(0)
    sys.exit()
elif M<2:
    print(1)
    sys.exit()

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

for i in range(2,M+1):
        ans *= countlist[i-1]**countlist[i]

print(ans%998244353)

Submission status: Accepted

Solution code:
import sys
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=[0] * (M + 1)
ans=1

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

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

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

for i in range(2,M+1):
    ans *= countlist[i-1]**countlist[i]

print(ans%998244353)

Submission status: Accepted

Solution code:
import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=list(map(int,np.zeros(M+1)))
ans=1

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

if countlist[0]!=1 :
    print(0)
    sys.exit()
elif M<2:
    print(1)
    sys.exit()

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

for i in range(2,M+1):
        ans *= countlist[i-1]**countlist[i]



print(ans%998244353)

Submission status: Accepted

Solution code:
import sys
import numpy as np
N = int(input())
D = list(map(int,input().split()))
M = max(D)
countlist=list(map(int,np.zeros(M+1)))
ans=1

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

if 0 in countlist or countlist[0]!=1 :
    print(0)
    sys.exit()
elif M<2:
    print(1)
    sys.exit()

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

for i in range(2,M+1):
    if countlist[i]>0:
        ans *= countlist[i-1]**countlist[i]
    elif i<M:
        ans=0
    else:
        break


print(ans%998244353)

Submission status: Accepted

Solution code:
def main():
    N = input()
    D_list = list(map(int, input().split()))

    if D_list[0] != 0:
        ans = 0
    
    else:
        maxD = max(D_list)
        count_ele_Dlist = [0] * (maxD + 1)

        for i in D_list:
            count_ele_Dlist[i] = count_ele_Dlist[i] + 1

        if count_ele_Dlist[0] == 1:
            ans = 1
            for i in range(1, maxD + 1):
                ans = (ans * count_ele_Dlist[i - 1] ** count_ele_Dlist[i]) % 998244353
        else:
            ans = 0
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys

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

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

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

patt = 1
for i in range(1, len(counter)):
    patt *= counter[i-1]**counter[i]

print(patt % mod)

Submission status: Accepted

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

mod = 998244353
n = int(input())
d = list(map(int, input().split()))
c = collections.Counter(d)
ans = 1

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

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

if max(d)+1 != len(c):
    print(0)
    sys.exit()

try:
    for i in range(1, len(c)-1):
        ans = (ans*c[i]**c[i+1]) % mod
except KeyError:
    print(0)
    sys.exit()

print(ans)

Submission status: Accepted

Solution code:
from math import factorial
def ncr(n,r):
 return factorial(n) // factorial(r) // factorial(n - r)
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  d = list(int(i) for i in input().split())
  if d[0] != 0:
    print(0)
    exit()
    
  mod = 998244353
  query = [0]*n
  length = 0
  for i in range(n):
    tmp = d[i]
    length = max(tmp,length)
    query[tmp] += 1
  if query[0] != 1:
     print(0)
     exit()
  
  ans = query[0]
  for i in range(1,length+1):
    next = query[i]
    if query[i-1] == 1:
      ans *= 1
    else:
      ans *= query[i-1]**next
    ans %= mod
  print(ans)
solve()

Submission status: Accepted

Solution code:
from collections import Counter

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

d = Counter(D)
Dmax = max(D)
ans = d[0]**d[1]
for i in range(1,Dmax):
	ans = (ans*d[i]**d[i+1])%998244353
if d[0] != 1 or D[0] != 0:
	ans = 0
print(ans)

Submission status: Accepted

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

dd = sorted(d)
c = []
j = 0
for i in range(max(d)+1):
	tmp = 0
	while dd[j] == i:
		tmp += 1
		j += 1
		if j == n:
			break
	c.append(tmp)

ans = 1
if d[0] == 0 and d.count(0) == 1 and c.count(0) == 0:
	for i in range(1, max(d)):
		ans = ans * (c[i]**c[i+1])
else:
	ans = 0

print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

ctr = Counter(D)

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

ans = 1
for i in range(len(ctr)-1):
    ans *= pow(ctr[i], ctr[i+1], MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
Z = 998244353
N = int(input())
D = list(map(int,input().split()))
if D[0]>0:
    ans = 0
elif N==1:
    ans = 1
else:
    D.sort()
    if D[1]==0:
        ans = 0
    else:
        D.append(-1)
        ans = 1
        cur = 0
        n1 = 1
        n2 = 1
        for d in D[1::]:
            if d == cur:
                n2 += 1
            else:
                if d == cur+1 or d == -1:
                    nn = pow(n1,n2,Z)
                    ans *= nn
                    n1 = n2
                    n2 = 1
                    cur = d
                else:
                    ans = 0
                    break
        ans%=Z
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
n = int(input())
d = list(map(int, input().split()))
c = [0] * n
for v in d:
    c[v] += 1
res = 0 if d[0] != 0 or c[0] != 1 else 1
for i in range(n - 1):
    res = res * c[i] ** c[i + 1] % MOD
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(s) for s in input().split(' ')]
counts = [0] * n
for i in a:
  counts[i] += 1
ans = 1 if a[0] == 0 and counts[0] == 1 else 0
for u, v in zip(counts, counts[1:]):
  for _ in range(v):
    ans = ans * u % 998244353
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
Q = [0]
for i in map(int, input().split()):
	if i >= len(Q):
		if Q[0] == 0:
			print(0)
			exit()
		Q += ([0] * (i + 1 - len(Q)))
	Q[i] += 1
mod = 998244353

sum = 1
for i in range(len(Q)):
	if Q[i] == 0:
		sum = 0
		break
	if i == 0:
		if Q[i] != 1:
			sum = 0
			break
		else:
			continue
	sum *= (Q[i-1] ** Q[i])
	sum %= mod

print(sum)

Submission status: Accepted

Solution code:
MD=998244353

import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

import numpy as np

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

C=[0]*(N)

for i in range(N):
  C[D[i]]+=1
#print(C)

tmp=1
for i in range(N-1):
  tmp*=(C[i]**C[i+1])
  tmp%=MD
answer=tmp

if N==1:
  answer=0 if C[0]!=0 else 1
for i in range(1,N):
  if D[i]==0:
    answer=0  

print(answer)

Submission status: Accepted

Solution code:
import sys

n = int(input())
d = list(map(int, input().split()))
counts = [0] * (max(d) + 1)
mod = 998244353

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

if counts[0] != 1 or d[0] != 0:
    print(0)
else:
    ans = 1
    for i in range(1, max(d) + 1):
        if counts[i] == 0:
            print(0)
            sys.exit()

        ans *= counts[i-1]**counts[i] % mod

    print(ans % mod)

Submission status: Accepted

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

H = copy(D)
H.sort()



if D[0] != 0: print(0)
elif H[0] == 0 and H[1] == 0: print(0)
else:
  D.sort()
  flg = True
  A = []
  a = 1
  c = 0
  for i in range(1,N):
    if D[i] == D[i-1] + 1:
      A.append(a)
      a = 1
      c += 1
    elif D[i] == D[i-1]:
      a += 1
    else:
      flg = False
      break
  
  A.append(a)
  c += 1

  ans = 1

  if flg:
    for i in range(1,c):
      ans *= (A[i-1]%998244353)**A[i]
    print(ans%998244353)

  else:
    print(0)

Submission status: Accepted

Solution code:
import numpy as np

mod = 998244353

n = int(input())
 
D = list(map(int, input().split()))
 
dic = [0] * n
for x in D:
    dic[x] += 1
 
if dic[0] != 1 or D[0] != 0:
    print(0)
    exit()
  
ans = 1
for i in range(1, n):
    if dic[i] == 0:
        if sum(dic[i:]) == 0:
            break
        else:
            print(0)
            exit()
 
    ans = (ans * pow(dic[i-1], dic[i], mod)) % mod
 
print(ans)

Submission status: Accepted

Solution code:
n = int(input().strip())
d = list(map(int, input().split()))
h = [0] * n
for x in d:
  h[x] += 1

ans = 1
mod = 998244353
for i in range(1, n):
  ans = (ans * pow(h[i-1], h[i], mod)) % mod

if h[0] != 1 or d[0] != 0:
  ans = 0

print (ans)

Submission status: Accepted

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

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

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

MOD = 998244353

r = [0] * (n+1)

for x in d[1:]:
    if x == 0:
        print(0)
        exit()
    else:
        r[x] += 1

mode = 0
for i in range(1, n+1):
    if mode == 0:
        if r[i] == 0:
            mode = 1
    else:
        if r[i] > 0:
            print(0)
            exit()

def mod_pow(x, y):
    bi = str(format(y, "b"))  # 2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res * res) % MOD
        if bi[i] == "1":
            res = (res * x) % MOD
    return res

ans = 1
for i in range(1, n+1):
    if r[i+1] == 0:
        break
    else:
        ans = (ans * mod_pow(r[i], r[i+1])) % MOD

print(ans)

Submission status: Accepted

Solution code:
Z = 998244353


def calc(N, D):
    if D[0] != 0:
        return 0
    d = {}
    for Di in D:
        d[Di] = 1 + (d[Di] if Di in d else 0)
    if d[0] != 1:
        return 0
    result = 1
    for i in range(max(d.keys())):
        if not i + 1 in d:
            return 0
        result *= (d[i] ** d[i + 1]) % Z
        result = result % Z
    return result


N = int(input())
D = [int(s) for s in input().split()]
print(calc(N, D))

Submission status: Accepted

Solution code:
# tempt
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
MOD = 998244353

N = int(readline())
D = np.array(read().split(),np.int32)

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

counter = np.bincount(D,minlength=N)

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

arr = counter[D[1:] - 1]

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

answer = cumprod(arr,MOD)[-1]
print(answer)

Submission status: Accepted

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

if Ds[0] != 0:
    print(0)
    exit()
Ds = sorted(Ds[1:])
c = Counter(Ds)
M = 998244353

r = p = i = 1
x = c.get(i)
while x:
    N -= x
    r = r * pow(p, x, M) % M
    i += 1; p = x; x = c.get(i)
print((r,0)[N>1])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0 or a.count(0)!=1:
  print(0)
else:
  a.sort()
  i=1
  j=1
  p=1
  q=0
  r=1
  while i<n:
    while a[i]==j:
      q+=1
      i+=1
      if i==n:
        break
    j+=1
    r*=p**q
    p=q
    q=0
  print(r%998244353)

Submission status: Accepted

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

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

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

for i in range(0, N-1):
    if abs(D[i] - D[i+1]) > 1:
        print(0)
        exit(0)

cnt = [0 for _ in range(N)]

for i in range(0, N):
    cnt[D[i]] += 1

ans = 1

for i in range(0, N-1):
    if cnt[i+1] == 0:
        break
    ans *= pow(cnt[i], cnt[i+1])
    ans %= 998244353

print(ans)

Submission status: Accepted

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

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

for k in range(1,N):
    if A[k] == 0:
        print(0)
        exit(0)

B = [0 for k in range(max(A)+1)]
for e in A:
    B[e] += 1

ans = 1
MOD = 998244353
for k in range(len(B)-1):
    ans *= pow(B[k],B[k+1],MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

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

ma = max(d)
l = [0] * n
ans = 1

#  1番上の頂点が無ければ0
if d[0] != 0:
    print(0)
    exit()

#  0~maxがそれぞれ何個あるか
for e in d:
    l[e] += 1

#  1番上の頂点が複数個だと0
if l[0] != 1:
    print(0)
    exit()

for i in range(ma):
    #  l[i]は辺の数でl[i+1]はノードの数
    ans = ans * l[i] ** l[i+1]
    ans = ans % 998244353
print(ans)

Submission status: Accepted

Solution code:
def find(D):
    if D[0]!=0:
        return 0
    
    count=[0 for _ in range(len(D))]
    MAX=max(D)
    
    ans=1
    for x in D:
        count[x]+=1
    
    if count[0]!=1:
        return 0
    
    for i in range(1,MAX+1):
        ans=ans*pow(count[i-1],count[i],998244353)
        ans%=998244353
    return ans
N=int(input())
D=list(map(int,input().strip().split()))
print(find(D))

Submission status: Accepted

Solution code:
n = int(input())
D = list(map(int,input().split()))
ma = max(D)
l = [0]*n
ans = 1

if D[0] != 0:
    print(0)
    exit()
    
for e in D:
    l[e] += 1

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

for i in range(ma):
    ans = ans * l[i] ** l[i+1]
    ans = ans % 998244353
print(ans)

Submission status: Accepted

Solution code:
# 指定された距離で何個の木を作成することができるかを計算する
import bisect
import itertools
N = int(input())
D = list(map(int, input().split()))
node_dis = [1] # 距離iのノードの個数をi番目の要素として格納したリスト
flag_none = False

# 頂点１から深さは決まっている.深さni毎に前のni-1のノードから重複を許してc_ni個選んでノードに繋げばよい
if not D[0] == 0:
    print(0)
    flag_none = True

else:
    D.sort()  # 昇順でソート
    for i in range(1,N):
        if i == 1 and bisect.bisect_left(D,1) >= 2:  # 0が２つ以上ある場合
            print(0)
            flag_none = True
            break
        else:
            if i ==1:
                del D[0]
            index = bisect.bisect_left(D,i+1)
            new_num = index 
            node_dis.append(new_num)
            del D[:index]
            if index==0: 
                if not D == []:
                    print(0)
                    flag_none = True
                break
if flag_none == False:
    sum = 1
    for (ind, di) in enumerate(node_dis): 
        if ind > 0:
            sum *= node_dis[ind-1] ** di
    print(sum%998244353)

Submission status: Accepted

Solution code:
N =int(input())
D = [int(x) for x in input().split()]
cnt = [0]*(N)
if D[0]!=0:
  print(0)
  exit()
for i in range(N):
  cnt[D[i]]+=1
ans = 1
if cnt[0]!=1:
  print(0)
  exit()
a = 0
b = 0
for i in range(1,N-1):
  if cnt[i]==0 and a==0:
    a=i
    b+=1
  if a!=0 and cnt[i]!=0:
    print(0)
    exit()
  elif a!=0 and cnt[i]==0:
    b+=1
  ans*=cnt[i-1]**cnt[i]
  ans%=998244353
#print(cnt,a,b)
if N-a==b or a==b==0:
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
N = int(input())
Ds = [int(s) for s in input().split(' ')]
MOD = 998244353
if Ds[0] != 0:
  print('0')
  exit(0)
for d in Ds[1:]:
  if d == 0:
    print('0')
    exit(0)

counts = [0] * (max(Ds) + 1)
for d in Ds:
  counts[d] += 1
  
ans = 1
for c1, c2 in zip(counts[:-1], counts[1:]):
  ans *= c1 ** c2
  ans %= MOD
  
print(ans)