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:
from collections import Counter
import sys
MOD = 998244353

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
#b = [int(i) for i in readline().split()]

wt = [0]*(n+2)
for i in a:
    wt[i] += 1

MOD = 998244353

ans = 1
cnt = 1

#print(wt)

for i,c in enumerate(wt):
    if i == 0:
        if c != 1:
            ans = 0
            break
        else: pass
    else:
        cnt += c
#        print(cnt,c)
        if cnt != n:
            if c == 0:
                ans = 0
                break
            else:
                ans *= pow(wt[i-1],c,MOD)
        else:
            ans *= pow(wt[i-1],c,MOD)
            break
    ans %= MOD    
#    print(i,c,ans,cnt)    


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


print(ans%MOD)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
D = np.array(list(map(int, input().strip().split())))

if D[0] == 0:
    count = [0] * (len(D)+1)
    max_d = max(D)
    for d in D:
        count[d] += 1

    if count[0] == 1:
        ans = 1
        for i in range(2,max_d+1):
            if count[i] <= 0:
                ans = 0
                break
            ans *= count[i-1]**count[i]

        print(ans%998244353)
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 998244353 
N = int(input())
D = [int(x) for x in input().split()]
zero = 0 
for d in D:
    zero += (d == 0)
if (D[0] != 0 or zero != 1):
    print(0)
else:
    lst = [0] * (N)
    for d in D:
        lst[d] += 1
    first0 = False
    for i in range(N):
        if (lst[i] != 0 and first0):
            print(0)
            exit()
        elif (lst[i] ==0):
            first0 = True
    ans = 1
    for i in range(N-1):
        ans *= lst[i] ** lst[i+1]
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))
C=[0]*N
for i in range(N):
    C[D[i]]+=1
ans=1
if D[0]>0 or C[0]>1:
    print(0)
else:
    for j in range(2,max(D)+1):
        if C[j-1]==1:
            continue
        else:
            ans*=C[j-1]**C[j]
    print(ans%998244353)

Submission status: Accepted

Solution code:
mod = 998244353
n=int(input())
d=[int(i) for i in input().split()]
ans=[0]*n
for i in d:
    ans[i]+=1
f=mod
for i in ans:
    if f==0 and i>0:
        print(0)
        exit()
    f=min(f,i)
if d.count(0)!=1 or d[0]!=0:
    print(0)
    exit()
cnt=1
if ans[2]==0:
    print(1)
    exit()
for i in range(1,n):
    if ans[i]==0:
        break
    cnt=cnt*pow(ans[i-1],ans[i],mod)%mod
 
print(cnt%mod)

Submission status: Accepted

Solution code:
import collections

n=int(input())
d=list(map(int, input().split())) 
mod= 998244353
ans=1 
if d[0]!=0:
    print(0)
    exit()
    
d.sort()
e = collections.Counter(d)
e = e.most_common()
e =list(e)
e.sort()

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


for i in range(1,len(e)):
    if e[i][0]-e[i-1][0]!=1:
        print(0)
        exit()
    
    else:
        ans*=(e[i-1][1])**e[i][1]
        ans=ans%mod
print(ans)

Submission status: Accepted

Solution code:
def modpow(a, n, mod):
    bi = format(n, 'b')
    res = 1
    for i in range(len(bi)):
        res = (res * res) % mod
        if bi[i] == '1':
            res = (res * a) % mod
    return res

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

L = [0] * (max(D) + 1)
for d in D:
    L[d] += 1

if (L[0] != 1) | (D[0] != 0):
    ans = 0
else:
    ans = 1
    for i in range(len(L)-1):
        ans *= modpow(L[i], L[i+1], mod)
        ans %= mod

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:
def solve():
    n = int(input())
    d = list(map(int, input().split()))

    print(calc(d, n))


def calc(d, n):
    if d[0] != 0:
        return 0
    else:
        k = max(d)
        a = [0] * (k + 1)
        for i in range(1, n):
            a[d[i]] += 1
        if a[0] > 0:
            return 0
        else:
            r = 1
            for i in range(2, k + 1):
                r *= a[i - 1] ** a[i]
            return r % 998244353


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
d = list( map(int, input().split()) )
MOD = 998244353

c = Counter(d)

def count(c, iter):
    if c[0] != 1 or d[0] != 0:
        return 0

    res = 1
    for i in range(2, iter+2):
        for _ in range(c[i]):
            res *= c[i-1]%MOD
        res %= MOD
    return res%MOD

res = count(c, max(d))
print(res)

Submission status: Accepted

Solution code:
n=int(input())
d=[int(x) for x in input().split()]
ans=True
if(d[0]!=0):
    ans=False
d.sort()
dd=[0]*10**5
max=0
for i in d:
    dd[i]+=1
    if(max<i):
        max=i

now=1
before=0
if(dd[0]!=1):
    ans=False
else:
    before=1

for i in range(1,max+1):
    if(dd[i]==0):
        ans=False
    now=now*(before**dd[i]) % 998244353
    before=dd[i]
    #print(dd[i],now)

if(ans):
    print(now)
else:
    print("0")

Submission status: Accepted

Solution code:
mod = 998244353

N = int(input())
D = [int(x) for x in input().split()]

dep = max(D)
dict = [0]*(dep+1)

for d in D:
    dict[d]+=1
if(dict[0]!=1 or D[0]!=0):
    ans = 0
else:
    ans = 1
    for de in range(1,dep+1):
        ans *= (dict[de-1]**dict[de])%mod
        ans %= mod
print(ans)

Submission status: Accepted

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

import sys
from collections import Counter

N=input()
D=map(int, sys.stdin.readline().split())
max_D=max(D)

C=Counter(D)
if C[0]!=1:
    print 0
    quit()

mod=998244353
if D[0]!=0:
    print 0
    quit()
else:
    ans=1
    for i in range(2,max_D+1):
        ans*=pow(C[i-1],C[i],mod)
        ans%=mod

print ans%mod

Submission status: Accepted

Solution code:
n, *d = map(int, open(0).read().split())
a = [0] * (n + 1)
for x in d:
	a[x] += 1
mod = 998244353
if a[0] != 1 or d[0] != 0:
	print(0)
	exit()
if n == 1:
	print(1)
	exit()
ans = 1
bef = 1
cnt = 1
for x in a[1:]:
	cnt += x
	if x == 0:
		if cnt == n:
			break
		else:
			print(0)
			exit()
	ans *= bef ** x
	ans %= mod
	bef = x
print(ans)

Submission status: Accepted

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

div_num = 998244353
result = 1
ct_l = []

for i in range(max(l)+1):
    ct_l.append(0)

for item in l:
    ct_l[item] += 1

#print(ct_l)
prev_v = -1
curr_v = -1
e = n-1

for i, item in enumerate(ct_l):
    if i == 2:
        break
    if i == 0 and item == 1:
        pass
    else:
        e -= item
    if i == 1:
        prev_v = item

for i, item in enumerate(ct_l[2:]):
    #print(prev_v, item, e, result)
    e -= item
    if item == 0:
        break
    curr_v = item
    result *= prev_v**curr_v
    result %= div_num
    prev_v = curr_v
    #print(prev_v, curr_v, result)

if e < 0 or e > 0 or l[0] > 0:
    print(0)
elif n == l[1]:
    print(1)
else:
    print(result)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
D=list(map(int,input().split()))
M=max(D)
l=[0]*(M+1)
for i in D:
    l[i]+=1
if l[0]==1 and D[0]==0:
    a=1
    for i in range(M):
        a*=pow(l[i],l[i+1],998244353)
    a%=998244353
    print(a)
else:
    print(0)

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
r = 0
if (a[0], c[0]) == (0, 1):
    r = i = 1
    while c[i]:
        r = r * pow(c[i - 1], c[i], M) % M
        n -= c[i]
        i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
import math
from collections import Counter
N=int(input())
D=input().split()
T=[]
D_dict=Counter(D)
D_keys=list(D_dict.keys())
D_keyi=[int(n) for n in D_keys]
maxD=max(D_keyi)
D_keyi.sort()
ans=1
if D[0] != '0' or D_dict['0']!=1 or D_keyi != list(range(maxD+1)):
    print(0)
else:
    for i in range(maxD+1):
        T.append(D_dict[str(i)])
    for i in range(len(T)-1):
        ans=ans*(T[i]**T[i+1])
    print((ans%998244353))

Submission status: Accepted

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

 
MOD = 998244353
 
occ = [0 for i in range(N+5)]
for d in D:
    occ[d] += 1
 
if occ[0] != 1 or D[0] != 0:
    print(0)
    quit()
 
cur = 1
for i in range(1, N+5):
    cur *= pow(occ[i - 1], occ[i])
    cur %= MOD
print(cur % MOD)

Submission status: Accepted

Solution code:
from math import factorial as fact
from collections import Counter
import sys

N = int( input() )
tree = list( map( int, input().split() ) )
ans = 1
if tree[0] != 0:
    print(0)
else:
    c = Counter(tree)
    if c[0] != 1:
        print(0)
    else:
        ans = 1
        a = c[0]
        for i in range( 1,len(c)):
            t = c[i]
            if t == 0:
                print(0)
                sys.exit()
            else:
                ans *= ( a**t )
                a = t
        print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
ans = 1
t = 1
if n == 1:
  if l[0] == 0:
    print(1)
  else:
    print(0)
 
elif n == 2:
  if l[0] ==0 and l[1] == 1:
    print(1)
  else:
    print(0)
 
else:
  if l[0] != 0:
    print(0)
  else:
    a = [0]*n
    for i in range(n):
      a[l[i]] += 1
 
    if a[0] != 1:
      print(0)
    else:
      for i in range(n-1):
        if a[i]==0 and a[i+1]!=0:
          t = 0
          
        elif a[i]!=0 and a[i+1]!=0:
          ans = ans * (a[i]**a[i+1])
      if t == 1:
        print(ans%998244353)
      else:
        print(0)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
if d[0] != 0:
    print(0)
else:
    import collections
    c = collections.Counter(d)
    c_sorted = sorted(c.items())
    u = [x[1] for x in c_sorted]
    u.remove(u[0])
    if len(u)!= max(d):
        print(0)
    else:
        if d.count(0) > 1:
            print(0)
        else:
            x = 1
            for i in range(len(u)-1):
                x = x * (u[i] ** u[i+1])
                 
            print(x%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 998244353

N = int(input())

nums = [int(x) for x in input().split(' ')]
if nums[0] != 0:
	print(0)
	exit()
	
nums.sort()
#print('yeah')

if N > 1 and nums[1] != 1:
	print(0)
	exit()
	
if N == 1:
	print(1)
	exit()
	


def pow_mod(m,n):
	prod = 1
	for i in range(n):
		prod = (m * prod) % mod
		
	return prod

count = 1
counts = []
cnt_current = 0
zero_count = 0
for num in nums[1:]:
	if num > count:
		counts.append(cnt_current)
		if num - count > 1:
			print(0)
			exit()
		cnt_current = 1
		count = num
	else:
		cnt_current += 1
		
if count > 1:
	counts.append(cnt_current)
		
#print(counts)
		
if count == 1:
	print(1)
	exit()
	
out = 1
for i in range(len(counts) - 1):
	out *= pow_mod(counts[i],counts[i+1]) % mod
	
print(out % mod)

Submission status: Accepted

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

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

    if D[1] == 0:
        print(0)
    else:
        mod = 998244353
        ans = 1
        distance = 0
        prev = 1
        now = 0

        for i in range(N):
            if D[i] == distance:
                now += 1
            elif D[i] == distance + 1:
                ans = (ans % mod) * (prev ** now % mod) % mod
                prev = now+0
                now = 1
                distance += 1
            else:
                ans = 0
                break
        else:
            ans = (ans % mod) * (prev ** now % mod) % mod
        
        print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
d = list(map(int, input().split()))
m = {}
ans = 1

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

if d.count(0) > 1:
    print(0)
    sys.exit()

for i in range(n):
    num = d[i]
    if num in m:
        m[num] += 1
    else:
        m[num] = 1

# if len(m) < n:
#     print(0)
#     sys.exit()

#print(m)
#print(max(m))
maxV = max(m.keys())

#for i in range(1, max(m)+1):
#for i in range(0, max(m)):
for i in range(0, maxV):
    if i not in m or i + 1 not in m:
        print(0)
        sys.exit()
    prevCnt = m[i]
    curCnt = m[i+1]
    # prevCnt = m[i] % 998244353
    #curCnt = m[i+1] % 998244353
    ans *= prevCnt ** curCnt
    #ans *= (prevCnt ** curCnt) % 998244353

print(ans % 998244353)

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
r = 0
if a[0] == 0 and c[0] == 1:
    r = i = 1
    while c[i]:
        r = r * pow(c[i - 1], c[i], M) % M
        n -= c[i]
        i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
import sys

def main():
    N = int(input())
    D = list(map(lambda i: int(i), input().split(' ')))
    # N = 100000
    # D = [0]
    # for i in range(1, N):
    #     D.append(i)

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

    ary = [0] * N
    for d in D:
        ary[d] = ary[d] + 1

    # 続いてなかったらNG
    zero = False
    for i in range(len(ary)):
        if ary[i] != 0 and zero is True:
            print(0)
            sys.exit()
        if ary[i] == 0 and zero is False:
            zero = True

    # 距離0は頂点1だけ
    if ary[0] != 1:
        print(0)
        sys.exit()

    answer = 1
    for i in range(1, len(ary)):
        for j in range(ary[i]):
            answer = (answer * ary[i - 1]) % 998244353
    print(answer)

main()

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)
  exit()
D=Counter(d)
l=len(D)

ans=1
for i in range(l):
  if i==0:
    if D[i]!=1:
      print(0)
      exit()
  else:
    if D[i]==0:
      print(0)
      exit()
    else:
      ans=(ans*((D[i-1]**D[i])%mod))%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import tee

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


def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


def is_leap(distance):
    cc = Counter(distance)
    for x, y in pairwise(sorted(cc.keys())):
        if y - x > 1:
            return True
    else:
        return False


if D[0] > 0:
    """頂点1が根ではない"""
    print(0)
elif not all(D[1:]):
    """連結グラフではない"""
    print(0)
elif is_leap(D):
    print(0)
else:
    ans = 1
    c = Counter(D[1:])
    edges = [t[1] for t in sorted(c.items())]
    for d, e in pairwise(edges):
        ans *= pow(d, e)
    print(ans % R)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
d = [int(_) for _ in input().split()]
c = Counter(d)
ans = 0
dmax = max(d)

f = 1
for i in range(dmax+1):
    f *= c[i]

if d[0] == 0 and c[0] == 1 and f:
    ans = 1
    if dmax > 1:
        for i in range(2, dmax+1):
            ans *= c[i-1]**c[i]
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 998244353

N = int(input())
D = list(map(int, input().split()))
C = Counter(D)
if D[0] != 0 or C[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, max(D)+1):
    if C[i] == 0:
        ans = 0
        break
    else:
        ans *= pow(C[i-1], C[i], MOD)
        ans %= MOD
print(ans)


# import sys
# sys.setrecursionlimit(10000000)
# def input():
#     return sys.stdin.readline()[:-1]
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
# INF = float('inf')
# # MOD = 10**9+7
# MOD = 998244353
#
# N = int(input())
# D = list(map(int, input().split()))
# if D[0] != 0:
#     print(0)
# C = Counter(D)
# ans = 1
# for i in range(1, max(D)+1):
#     if C[i] == 0:
#         ans = 0
#         break
#     else:
#         ans *= pow(C[i-1], C[i], MOD)
#         ans %= MOD
# print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections


N=int(input())
D=list(map(int,input().split()))
A=collections.Counter(D)
if D[0]==0 and len(set(D))==max(D)+1 and A[0]==1:
  c=1
  for i in range(max(D)):
    c*=A[i]**A[i+1]
  ans=c%998244353  
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from math import factorial
from fractions import Fraction
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


MOD = 998244353
n = INT()
d = LIST()
if d[0] != 0:
    print(0)
    sys.exit()
d = d[1:]
c = dict(Counter(d))
c =  OrderedDict(sorted(c.items()))
c = list(c.values())
if len(c) != max(d):
    print(0)
    sys.exit()
res = 1
for i in range(1, len(c)):
    res *= c[i-1]**c[i]

print(res%MOD)

Submission status: Accepted

Solution code:
import sys
import collections
def solve():
    sys.setrecursionlimit(100000)
    mod = 998244353

    N = int(input())
    D = list(map(int, input().split()))
    ans = 1
    if D[0] != 0:
        ans = 0
        print(ans)
        exit(0)
    
    cnter = collections.Counter(D)
    cnter = sorted(cnter.items())

    if cnter[0][0] != 0 or cnter[0][1] != 1 : 
        ans = 0
    elif len(cnter) == 1:
        ans = 1
    elif cnter[1][0] != 1:
        ans = 0
    else:
        for i in range(2, len(cnter)):
            if cnter[i][0] != i:
                ans = 0
                break

            else:
                ans = ans * modpow(cnter[i-1][1], cnter[i][1], mod) % mod
    
    print(ans)


def modpow(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans = ( ans * num_at_dist[dist - 1] ) % 998244353

print(ans % 998244353)

Submission status: Accepted

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

for i in range(1, n):
    if l[i] == 0:
        print(0)
        exit()

max_vertex = max(l)
ll = []
l=sorted(l)
l.append(-4)
c=1
for i in range(1, n):
    if l[i] != l[i+1]:
        if l[i] != l[i+1]-1 and l[i+1] > 0:
            print(0)
            exit()
        ll.append(c)
        c = 0
    c+=1

count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
if a[0] == 0 and c[0] == 1:
    r = i = 1
    while c[i]:
        r = r * pow(c[i - 1], c[i], M) % M
        n -= c[i]
        i += 1
print(r if n == 1 else 0)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
s = input()
if s[0] != '0':
    print(0)
    exit()

d = Counter(map(int, s.split()))
mod = 998244353

if 0 not in d or d[0] > 1:
    print(0)
    exit()
if n == 1:
    print(1)
    exit()

ans = 1
for i in range(1,len(d)):
    if i not in d:
        print(0)
        exit()
    ans = (ans * d[i-1]**d[i]) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
import collections
 
n = int(input())
d = list(map(int, input().split()))
for i in range(len(d)):
    if i == 0 and d[i] != 0:
        print(0)
        exit()
    if i != 0 and d[i] == 0:
        print(0)
        exit()
 
e = collections.Counter(d)
 
e2 = dict(sorted(e.items()))
e3 = list(e2.values())
e4 = list(e2.keys())
# print(e2)
#print(e3)
#print(e4)
 
tmp = 0
for i in e4:
    if i - tmp >= 2:
        print(0)
        exit()
    tmp = i
cntsum = 1
for i in range(1, len(e3)):
    cntsum *= e3[i - 1] ** e3[i]
print(cntsum%998244353)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
D=list(map(int,input().split()))
if D[0]==0 and D.count(0)==1:
    D.sort()
    m=max(D)
    counter=[]
    for i in range(m+1):
        counter.append(bisect.bisect_right(D,i)-bisect.bisect_left(D,i))
    ans=1
    for i in range(1,m+1):
        ans*=counter[i-1]**counter[i]
    print(ans%998244353)
else:
    print(0)

Submission status: Accepted

Solution code:
mod = 998244353
n=int(input())
d=[int(i) for i in input().split()]
ans=[0]*n
for i in d:
    ans[i]+=1
f=mod
for i in ans:
    if f==0 and i>0:
        print(0)
        exit()
    f=min(f,i)
if d.count(0)!=1 or d[0]!=0:
    print(0)
    exit()
cnt=1
for i in range(1,n):
    if ans[i-1]==0:
        break
    cnt=cnt*pow(ans[i-1],ans[i],mod)%mod

print(cnt%mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
lim = 998244353
N=int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    sys.exit()
E = D[1:]
d = dict(Counter(E))
sum_=1
temp=1
max_n=max(d.keys())
if len(d) ==1:
    if list(d.keys()) == [0]:
        print(0)
        sys.exit()
if 0 in d.keys():
    print(0)
    sys.exit()
for i in range(1,max_n+1):
    try:
        add = (temp ** d[i]) % lim
        sum_ = (sum_ * add) % lim
        temp = d[i]
    except:
        print(0)
        sys.exit()
print(sum_)

Submission status: Accepted

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

if d[0] != 0 or d.count(0) != 1:
    print(0)
else:
    d.sort()
    ans = 1
    nx = 0
    pre = 1
    cnt = 0
    for i in range(n):
        if d[i] == nx:
            cnt += 1
        else:
            if d[i] == nx + 1:
                ans = ans * pre ** cnt
                pre = cnt
                cnt = 1
                nx += 1
            else:
                ans = 0
                break
    ans = ans * pre ** cnt
    print(ans%wari)

Submission status: Accepted

Solution code:
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

if L[0] != 0 or any(l == 0 for l in L[1:]):
    print(0)
    exit()

C = Counter(L)
MOD = 998244353
ans = 1
for i, j in enumerate(range(1, max(L)+1)):
    prev = C[i]
    cur = C[j]
    ans *= prev**cur
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
    print(0)
    exit()
c=Counter(d)
c=sorted(c.items(),key=lambda x:x[0])
if c[0]!=(0,1):
    print(0)
    exit()
ans=1
check=1
for i in range(1,len(c)):
    if c[i][0]!=check:
        print(0)
        exit()
    check+=1
    ans*=c[i-1][1]**c[i][1]
    ans%=998244353
print(ans%998244353)

Submission status: Accepted

Solution code:
MOD = 998244353
N = int(input())
*D, = map(int, input().split())
if D[0] != 0: print(0)
else:
    D = sorted(D)
    levels = [0 for _ in range(D[-1]+1)]
    for d in D:
        levels[d] += 1
    if 0 in levels or levels[0] > 1: print(0)
    else:
        ans = 1
        for l1, l2 in zip(levels, levels[1:]):
            ans = (ans * pow(l1, l2, MOD)) % MOD
        print(ans)

Submission status: Accepted

Solution code:

divider = 998244353

num = int(input())
depths = [int(x) for x in input().split()]
max_depth = max(depths)

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

if max_depth == 0:
  print(0)
  exit(0)

nodes = [0] * (max_depth+1)

for depth in depths:
  nodes[depth] += 1

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

arr = [nodes[i] ** nodes[i+1] for i in range(max_depth)]

ans = 1
for a in arr:
  ans = (ans * a)  % divider

print(ans)
exit(0)

Submission status: Accepted

Solution code:
from collections import Counter

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

L = sorted(set(D))
d = Counter(D)
s = 0

if (D[0] == 0) and (list(range(max(D) + 1)) == L):
    if (d[0]==1) and (1 in d):
        s = 1
        for l in L[1:-1]:
            for i in range(d[l + 1]):
                s *= d[l]
                s %= 998244353
print(s)

Submission status: Accepted

Solution code:
import collections


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

c = collections.Counter(D)

max_D = max(D)
ans = 1
previous_leaf = 1

if D[0] != 0:
    ans = 0
elif c[0] != 1:
    ans = 0
else:
    for i in range(1, max_D+1):
        ans *= (previous_leaf ** c[i])
        previous_leaf = c[i]

print(ans % 998244353)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = list(map(int,input().split()))
D_ = collections.Counter(D)
ans = 1
ans_ = 1
for i in range(len(D_)):
    temp = D_[i]
    if D[0] != 0:
        print(0)
        ans_ = 0
        break
    elif i == 0 and temp > 1:
        print(0)
        ans_ = 0
        break
    elif temp ==0:
        print(0)
        ans_ = 0
        break
    elif i > 0:
        ans *= D_[i-1] ** D_[i]
        ans %= 998244353
if ans_:
    print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = list(map(int,input().split()))
if D[0] == 0:
    if D.count(0) == 1:
        A = collections.Counter(D)
        result = 1
        for i in range(max(D)):
            result *= A[i] ** A[i + 1]
        print(result % 998244353)
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

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

r = [None] * N
m = 0

for i, j in enumerate(D):
    if (i == 0 and j != 0) or (i != 0 and j == 0):
        print("0")
        exit()
    r[j] = 1 if r[j] is None else r[j] + 1
    if j > m:
        m = j

result = 1
pre = None

for i, x in enumerate(r):
    if x is None:
        if i != m + 1:
            print("0")
            exit()
        else:
            break
    if i < 2:
        pre = x
        continue
    result *= pre**x
    pre = x

print(result % 998244353)

Submission status: Accepted

Solution code:
import collections

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

cnt = collections.Counter(D)

if D[0] != 0:
    ans = 0
elif cnt[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, max(D)+1):
        if cnt[i] == 0:
            ans = 0
            break
        else:
            ans *= cnt[i-1] ** cnt[i]

print(ans%998244353)

Submission status: Accepted

Solution code:
import collections


def mod_pow(a, n, mod):
    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def main(n, d):
    MOD = 998244353
    counter = collections.Counter(d)
    if counter[0] != 1 or d[0] != 0:
        return 0
    pows = [mod_pow(a=counter[i - 1], n=counter[i], mod=MOD) for i in
            range(1, max(counter.keys()) + 1)]
    patterns = 1
    for p in pows:
        patterns *= p
        patterns %= MOD
    return patterns


if __name__ == '__main__':
    N = int(input())
    D = list(map(int, input().split()))
    print(main(n=N, d=D))

Submission status: Accepted

Solution code:
mod=998244353
def modpow(a,r):
    ret=1
    while r>0:
        if r%2==1:
            ret*=a
            ret%=mod
        a*=a
        a%=mod
        r//=2
    return ret
n=int(input())
ds=[int(i) for i in input().split()]
if ds[0]!=0:
    print(0)
else:
    ma=max(ds)
    cnt=[0 for i in range(ma+1)]
    for i in ds:
        cnt[i]+=1
    if cnt[0]!=1 or min(cnt)==0:
        print(0)
    else:
        res=1
        for i in range(1,ma+1):
            res*=modpow(cnt[i-1],cnt[i])
            res%=mod
        print(res)

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)
    exit()
for d in D[1:]:
    if d==0:
        print(0)
        exit()
C=Counter(D)
m=max(D)
ans=1
for i in range(2,m+1):
    ans*=pow(C[i-1],C[i],mod)
    ans%=mod
print(ans)

Submission status: Accepted

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

dict = {}
for i in range(N):
    if list[i] in dict.keys():
        dict[list[i]] += 1
    else:
        dict.setdefault(list[i], 1)

max = max(dict)

try:
    for i in range(1,max+1):
        ans = (ans * (dict[i-1] ** dict[i])) % 998244353
    if dict[0] != 1:
        ans = 0
    if list[0] != 0:
        ans = 0
except KeyError:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:


def solve():
    N = int(input())
    D = [int(i) for i in input().split()]
    # 対象となる木のパターン数のチェック
    mD = max(D)
    nD = [0] * (mD + 1)
    for d in D:
        nD[d] += 1
    # 頂点が1でなくてはならない
    if D[0] != 0:
        print(0)
        return
    # 頂点が複数あってはならない
    if nD[0] != 1:
        print(0)
        return
    count = nD[0]
    for i in range(2, len(nD)):
        count *= nD[i - 1] ** nD[i]
        count = count % 998244353
    print(count)


if __name__ == '__main__':
    solve()