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:
N = int(input())
*D, = map(int, input().split())
MOD = 998244353

import collections
dic = collections.Counter(D)

flag = 1 if dic[0] != 1 or D[0] != 0 else 0
ans = 1
for d in range(1, max(D)+1):
    ans *= pow(dic[d-1], dic[d], MOD)
    ans %= MOD

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
cnt = 0
if (D[0]==0) and (D.count(0)==1):
  D = Counter(D)
  cnt = 1
  ans = 1
  for i in range(1, max(D)+1):
    if D[i] == 0:
      ans = 0
      break
    else:
      ans *= cnt ** D[i]
      cnt = D[i]
ans = ans % 998244353
print(ans)

Submission status: Accepted

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

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

D = sorted(D)
V = [0]*(D[-1]+1)

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

if V[0] > 1:
	print(0)
	exit()
else:
	count = 1

for i in range (0, len(V)-1):
	if V[i] == 0 and V[i+1] > 0:
		print(0)
		exit()
	else:
		count*= V[i]**V[i+1]
        
print(count%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
edge = [0 for x in range(n)]

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

for i in l:
    edge[i]+=1

ans = 1
for i in range(1, n):
    ans *= edge[l[i] - 1]
    ans %= 998244353
print(ans)

Submission status: Accepted

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

e = [0 for i in range(n)]

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

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

# print(e)

ans = 1

for i in range(1, n):
    ans *= e[d[i] - 1]
    ans %= 998244353
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
if a[0]!=0:
  print(0)
  quit()
#a.sort()
l=max(a)+1
dp1 = [0]*l
dp2 = [0]*l
ans=0
for i in a:
  dp1[i]+=1
#print(dp1)  

if dp1[0]!=1:
  print(0)
  quit()

dp2[0]=1
#print(dp2)
for i in range(1, l):
  dp2[i]=dp2[i-1]*(dp1[i-1]**dp1[i])
  dp2[i]%=mod

#print(dp2)
print(dp2[l-1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def run():
    N = int(sysread())
    D = list(map(int, sysread().split()))
    mod = 998244353
    dict = defaultdict(lambda:[])
    max_depth = 0
    for node, d in enumerate(D, 1):
        dict[d].append(node)
        max_depth = max(max_depth, d)
    if dict[0] != [1]:
        print(0)
        return None

    ans = 1
    for i in range(1, max_depth+1):
        pre = len(dict[i-1])
        current = len(dict[i])
        val =pow(pre, current, mod)
        ans *= val
        ans %= mod
    print(ans)
    return None

    #print(factorials)
if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()
    
    n = int(input()) 
    d = list(map(int, input().split()))
    mod = 998244353
    from collections import Counter as cc
    c = cc(d)
    if c[0] != 1 or d[0] != 0:
        print(0)
        return
    m = max(d)
    ans = 1
    for i in range(1, m+1):
        ans *= pow(c[i-1], c[i], mod)
        ans %= mod
    print(ans)
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    D = LI()
    mod = 998244353

    C = [0] * (N+1)
    for d in D:
        C[d] += 1
    # print(C)

    # 木が存在するかを判定
    ans = 1
    p = C[0]
    if not(D[0] == 0 and p == 1):
        print(0)
        return
    for i in range(1, N):
        ci = C[i]
        p = ci
        ans = ans * pow(C[i], C[i+1], mod)
    print(ans % mod)


    

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
lst=list(map(int,input().split()))
dist=[[] for _ in range(n)]
for i in range(n):
    dist[lst[i]].append(i)
if len(dist[0])!=1:
    print(0)
    exit()
if not 0 in dist[0]:
    print(0)
    exit()

switch=0
for i in range(-1,-n-1,-1):
    if switch==0:
        if len(dist[i])>=1:
            switch=1
    if switch==1:
        if len(dist[i])==0:
            print(0)
            exit()
ans=1
rem=1
for i in range(n):
    num=len(dist[i])
    ans*=pow(rem,num,998244353)
    ans%=998244353
    rem=num
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

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

Submission status: Accepted

Solution code:
from collections import Counter

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

mod = 998244353
c = Counter(D)
m = max(c.keys())

if D[0] == 0 and c[0] == 1:
    ans = 1
    for i in D[1:]:
        ans *= c[i-1]
        ans %= mod
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
# ？？？？？？？？？？？？？？？？？？？？？？？？？？
# ケース12と13、完全にバグとしか思えないのですが?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

# もしかして：頂点1は必ず0？

n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
    print(0)
    exit()
a = sorted(a)
d = {}
for av in a:
    if av not in d:
        d[av] = 1
    else:
        d[av] += 1

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

ans = 1
for i in range(1, a[-1] + 1):
    if i not in d:
        ans = 0
        break
    ans *= pow(d[i - 1], d[i], MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
# ？？？？？？？？？？？？？？？？？？？？？？？？？？
# ケース12と13、完全にバグとしか思えないのですが?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

# もしかして：頂点1は必ず0？

n = int(input())
a = list(map(int, input().split()))
if a[0] != 0:
    print(0)
    exit()
a = sorted(a)
d = {}
for av in a:
    if av not in d:
        d[av] = 1
    else:
        d[av] += 1

if a[0] != 0 or d[0] != 1 or len(set(d.keys())) != a[-1] + 1:
    print(0)
    exit()
MOD = 998244353
ans = 1
for i in range(2, a[-1] + 1):
    ans *= pow(d[i - 1], d[i], MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import Counter

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

MOD = 998244353

def main():
    N = II()
    D = LII()

    if D[0] != 0 or D.count(0) > 1:
       print(0)
       return 
    
    c = Counter(D)
    res = 1

    if c[0] > 1:
       print(0)
       return
    
    mx = max(c.keys())
    for i in range(1, mx+1):
        if i not in c:
            print(0)
            return
        
        res = (res * c[i-1] ** c[i]) % MOD

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n, *d = map(int, open(0).read().split())
MOD = 998244353
c = Counter(d)
if d[0] != 0 or c[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, max(d)+1):
        ans *= (c[i-1] ** c[i]) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 998244353


def resolve():
    n = int(input())
    D = list(map(int, input().split()))
    MAX_L = max(D) + 1
    cnt = [0] * MAX_L

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

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

    res = 1
    for i in range(1, MAX_L):
        if cnt[i] == 0:
            print(0)
            break
        res *= pow(cnt[i - 1], cnt[i], mod)
        res %= mod
    else:
        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
D = tuple(map(int, input().split()))
maxd = max(D)
mod = 998244353
cd = [0] * (maxd+1)
for d in D:
    cd[d] += 1

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

ans = 1
for i in range(1, maxd+1):
    nodes = cd[i]
    ans *= pow(pre_nodes, nodes, mod)
    ans %= mod
    pre_nodes = nodes
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, ddd):
    if ddd[0] != 0:
        return 0
    cnt = Counter(ddd)
    if cnt[0] != 1:
        return 0
    max_c = max(cnt)
    for i in range(max_c + 1):
        if i not in cnt:
            return 0

    MOD = 998244353
    ans = 1
    for i in range(max_c):
        prev = cnt[i]
        curr = cnt[i + 1]
        ans = ans * pow(prev, curr, MOD) % MOD
    return ans


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

print(solve(n, ddd))

Submission status: Accepted

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

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

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

tmp = sorted(cd.items(), key=lambda x: x[0])

prev = -1
for i, _ in tmp:
    if i == prev + 1:
        prev = i
    else:
        print(0)
        exit(0)


ans = 1
# print(tmp)
# print(cd)
# for kx in range(2, max(D)+1):
for kx in range(2, len(tmp)):
    # print(kx)
    __, p = tmp[kx-1]
    _, v = tmp[kx]
    # p = cd[kx-1]
    # v = cd[kx]
    # print("{}^{}".format(p, v))
    while v > 0:
        ans *= p
        ans %= M
        v -= 1
# print(cd)

# for kx in range(1, max(D)+1):
#     ans *= pow(cd[kx-1], cd[kx],M)
#     ans %= M

print(ans)

Submission status: Accepted

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

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

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

tmp = sorted(cd.items(), key=lambda x: x[0])

ans = 1
for kx in range(2, max(D)+1):
# print(tmp)
# for kx in range(2, len(tmp)):
    # print(kx)
    # __, p = tmp[kx-1]
    # _, v = tmp[kx]
    p = cd[kx-1]
    v = cd[kx]
    # print("{}^{}".format(p, v))
    while v > 0:
        ans *= p
        ans %= M
        v -= 1
# print(cd)

# for kx in range(1, max(D)+1):
#     ans *= pow(cd[kx-1], cd[kx],M)
#     ans %= M

print(ans)

Submission status: Accepted

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

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

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

tmp = sorted(cd.items(), key=lambda x: x[0])

ans = 1
for kx in range(1, max(D)+1):
    # __, p = tmp[kx-1]
    # _, v = tmp[kx]
    p = cd[kx-1]
    v = cd[kx]
    # print("{}^{}".format(p, v))
    while v > 0:
        ans *= p
        ans %= M
        v -= 1
# print(cd)

# for kx in range(1, max(D)+1):
#     ans *= pow(cd[kx-1], cd[kx],M)
#     ans %= M

print(ans)

Submission status: Accepted

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

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

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

tmp = sorted(cd.items(), key=lambda x: x[0])

ans = 1


for kx in range(1, max(D)+1):
    ans *= pow(cd[kx-1], cd[kx],M)
    ans %= M

print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    N = int(input())
    D = list(map(int, input().split(' ')))
    max_d = max(D)
    counter = [0] * (max_d + 1)
    for d in D:
        counter[d] += 1
    if D[0] != 0 or counter[0] != 1:
        print(0)
        return
    ans = 1
    for d in range(1, max_d + 1):
        ans *= pow(counter[d - 1], counter[d], MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
d = list(map(int, input().split()))
cnt = defaultdict(int)
if d[0] != 0:
    print(0)
else:
    ans = 1
    for i in range(n):
        cnt[d[i]] += 1
    for i in range(1, n):
        ans = (ans * cnt[d[i] - 1] % 998244353)

    print(ans)

Submission status: Accepted

Solution code:
import collections
N=int(input())
D=list(map(int,input().split()))
mod=998244353
if D[0]!=0:
  print(0);exit()

D=collections.Counter(D)
if D[0]!=1:
  print(0);exit()
ans=1
for i in range(1,len(D)): 
  ans*=pow(D[i-1],D[i],mod)
  ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 998244353

def solve():
    if D[0] != 0 or 0 in D[1:]:
        print(0)
        return

    tree_dict = dict()
    max_dist = 0
    for idx, dist in enumerate(D):
        tree_dict[dist] = tree_dict.get(dist, 0) + 1
        max_dist = max(max_dist, dist)
    ret = 1

    for dist in range(max_dist + 1):
        if not dist in tree_dict:
            print(0)
            return
        ret = (ret * pow(tree_dict.get(dist - 1, 1), tree_dict[dist])) % MOD
    print(ret)

if __name__ == "__main__":
    N = int(input())
    D = list(map(int, input().split()))
    solve()

Submission status: Accepted

Solution code:
MOD = 998244353

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

max_d = max(d_lst)
lst = [0 for _ in range(max_d + 1)]
for d in d_lst:
    lst[d] += 1
if lst[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(max_d):
    ans *= pow(lst[i], lst[i + 1], MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

mod = 998244353
c = Counter(D)
m = max(c.keys())

if D[0] == 0 and c[0] == 1:
  ans = 1
  for i in D[1:]:
    ans *= c[i-1]
    ans %= mod
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
from collections import Counter

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

mod = 998244353
c = Counter(D)
m = max(c.keys())

if D[0] == 0 and c[0] == 1:
  ans = 1
  for i in range(1, m+1):
    ans *= c[i-1]**c[i]
    ans %= mod
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
from collections import Counter

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

mod = 998244353
c = Counter(D)
m = max(c.keys())

if D[0] == 0 and c[0] == 1:
  ans = 1
  for i in range(1, m+1):
    ans *= c[i-1]**c[i] % mod
    ans %= mod
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
from collections import Counter

N,*D = map(int, open(0).read().split())
m = 998244353
if D[0] > 0:
    print(0)
else:
    dc = Counter(D)
    dci = [x for x in dc.items()]
    ans = 1
    if dc[0] > 1:
        print(0)
    else:
        for i in range(1,max(dci)[0]+1):
            if dc[i] == 0:
                print(0)
                break
            else:
                ans = (ans*pow(dc[i-1],dc[i],m)) % m
        else:
            print(ans)

Submission status: Accepted

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

if Dc[0]!=1 or D[0]!=0:
    print(0)
else:
    for i in range(max(D)):
        ans = ans*pow(Dc[i],Dc[i+1])%mod
    print(ans%mod)

Submission status: Accepted

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

c = Counter(D)

mod = 998244353

L = list(set(D[:]))

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

if (c[0] > 1):
    print(0)
    exit()

if (N == 1):
    print(1)
    exit()

ans = []
for i in L:
    if (i == 0):
        break
    else:
        ans.append(c[i - 1] ** c[i])

# print(ans)
if (len(ans) == 0):
    print(0)
    exit()

multi_ans = 1
for i in ans:
    multi_ans *= i

print(multi_ans % mod)

Submission status: Accepted

Solution code:
from collections import Counter
 
mod = 998244353
 
def solve():
    N = int(input())
    Ds = list(map(int, input().split()))
    # 頂点1から頂点1は必ず深さ0
    if Ds[0] != 0:
        print(0)
        return
    
    counter = Counter(Ds)
    ret = 1
 
    if counter[0] > 1:
        print(0)
        return
    max_key = max(counter.keys())
    for i in range(1, max_key+1):
        if i not in counter:
            print(0)
            return
        
        ret = (ret*(counter[i-1]**counter[i]))%mod
        
    print(ret)
    
solve()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
D = LIST()

d = Counter(D)

if D[0] != 0 or 2 <= d[0]:
	print(0)
	exit()

ans = 1

for i in range(1, max(d.keys())+1):
	ans = ans * pow(d[i-1], d[i], mod) % mod
	tmp = d[i]

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    D = in_nl()
    mod = 998244353

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

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

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

    zero = N + 1
    non_zero = -1
    for i in range(N):
        if count[i] == 0:
            zero = min(zero, i)
        else:
            non_zero = max(non_zero, i)

    if zero < non_zero:
        print(0)
        exit()

    ans = 1
    for i in range(1, N):
        if count[i] == 0:
            break
        else:
            ans *= count[i - 1] ** count[i]
            ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353

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

if D[0] != 0:
    print(0)
else:
    nums = [0]*n
    for d in D:
        nums[d] += 1
    
    imp = False
    end = False
    
    if nums[0] > 1:
        imp = True
        
    for i in range(1,n):
        if nums[i] == 0:
            end = True
        else:
            if end:
                imp = True
                break
            
    if imp:
        print(0)
    else:
        ans = 1
        for i in range(1,n):
            if nums[i] == 0:
                break
            ans = ans*pow(nums[i-1], nums[i], mod)%mod
        print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
D = LIST()

d = Counter(D)

if d[0] == 1 and D[0] == 0:
	pass
else:
	print(0)
	exit()

ans = 1
tmp = 1
for i in range(max(d.keys())+1):
	ans = ans * pow(tmp, d[i], mod) % mod
	tmp = d[i]

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
N = int(input())
D = list(map(int,input().split()))
lis = [0] * (max(D)+1)
if D[0] != 0:
    print(0)
    exit()
for i in D:
    lis[i] += 1
if lis[0] == 0 or lis[0] > 1:
    print(0)
    exit()


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

Submission status: Accepted

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

def power(x,n,MOD):
    res=1
    if n>0:
        res=power(x,n//2,MOD)
        if (n%2==0):
            res=(res*res)%MOD
        else:
            res=(((res*res)%MOD)*x)%MOD
    #print(x,n,MOD,res)
    return res

def main(n,d):
    MOD=998244353
    hist=[0]*(n+1)
    maxd=0
    for i in range(n):
        hist[d[i]]+=1
        maxd=max(maxd,d[i])
    #print(hist,maxd)

    ans=1
    if hist[0]>1:
        return 0
    if d[0]!=0:
        return 0
    for i in range(1,maxd+1):
        #print(i, hist[i-1], hist[i])
        ans=(ans*power(hist[i-1], hist[i], MOD))%MOD
        #print(ans)

    return ans

if __name__=='__main__':
    n,d=readinput()
    ans=main(n,d)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
D = list(map(int,input().split()))
C = Counter(D)
mod = 998244353
ans = 1
D_max = max(D)

if D[0] != 0 or C[0] != 1:
    print(0)
    exit()
"""
def make_factorial_table(n):
    result = [0] * (n+1)
    result[0] = 1
    for i in range(1,n+1):
        result[i] = result[i-1] * i % mod
    return result

def nCr(n,r):
    return fact[n] * pow(fact[n-r],mod-2,mod) * pow(fact[r],mod-2,mod) % mod

fact = make_factorial_table(2*N)
"""

for i in D[1:]:
    ans *= C[i-1]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


N = int(input())
D = list(map(int, input().split()))
p = 998244353
count = Counter(D)

if D[0] != 0 or len(set(D)) != max(D) + 1 or count[0] > 1:
    ans = 0
else:
    count = sorted(count.items(), key=lambda x: x[0])
    ans = 1
    for i in range(len(count) - 1):
        x = count[i][1]
        y = count[i + 1][1]
        ans *= x ** y
        ans %= p

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    D = [int(item) for item in input().split()]
    d_dict = collections.Counter(D)

    cnt = 0
    if D[0] != 0:
        pass
    else:
        cnt = 1
        for i in D[1:]:
            cnt *= d_dict[i-1]
            cnt %= 998244353


    print(cnt % 998244353)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int, input().split()))
if D[0]!=0:
    print(0)
    exit()
if 0 in D[1:]:
    print(0)
    exit()
D=sorted(D)
p=998244353
edge=[0]*(N)

ans=1
for i in range(N):
    d=D[i]
    if i==0:
        if d==0:
            edge[0]+=1
            continue
        else:
            print(0)
            exit()
    if d==0:
        print(0)
        exit()
    if edge[d-1]==0:
        print(0)
        exit()
    else:
        edge[d]+=1
        ans*=edge[d-1]
        ans%=p

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
m = 998244353
import collections
c = collections.Counter(d)
if c[0] == 1 and d[0] == 0:
    ans = 1
else:
    ans = 0
d = sorted(d)
for i in range(1,n):
    ans *= c[d[i]-1]
    ans %= m
print(ans)

Submission status: Accepted

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

c=dict(Counter(d))
c=sorted(c.items(),key=lambda x: x[0])


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

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

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

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

print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
# N = 4
# D = [0, 3, 2, 1, 2, 2, 1]

from collections import Counter
import sys

C = Counter(D)

if C[0] != 1:
    print(0)
elif D[0] != 0:
    print(0)
else:
    CL = sorted(C.items())
    num_prev = -1
    val_prev = 1
    ans = 1
    for item in CL:
        num = item[0]
        val = item[1]
        if num != num_prev + 1:
            print(0)
            sys.exit()
        else:
            ans *= val_prev**val
            num_prev = num
            val_prev = val
    print(ans%998244353)