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
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)
        ans = ans % R
    print(ans % R)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*n
for i in a:
    cnt[i] += 1

output = 1
if a[0] != 0 or cnt[0] != 1:
    print(0)
elif max(a) == 1:
    print(1)
else:
    for i in range(2, n):
        output *= cnt[i-1]**cnt[i]
        output %= 998244353
    print(output)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
mod = 998244353


def main():
    N = I()
    A = LI()

    if A[0] != 0:
        return 0

    DistCnt = [0] * (max(A)+1)
    for i in range(N):
        DistCnt[A[i]] += 1

    if DistCnt[0] != 1:
        return 0

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

if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

num_dict = {}
ans = 1

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

if num_dict.get(0) == None or num_dict.get(0) >= 2 or D[0] != 0:
  ans = 0
else:
  for i in range(1,len(num_dict)):
    if num_dict.get(i) == None:
      ans = 0
      break
    else:
      ans *= num_dict.get(i-1) ** num_dict.get(i)

print(ans%998244353)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
M = [0]*N
for d in D: M[d]+=1

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

ans = 1
mod = 998244353
for i in range(1,N):
    ans *= (M[i-1]**M[i])
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# nikkei2019-2-qualB - Counting of Trees
from collections import Counter


def main():
    N, *D = map(int, open(0).read().split())
    MOD = 998244353
    cnt = Counter(D)
    if D[0] != 0 or cnt[0] > 1:
        ans = 0
    else:
        ans = 1
        for i in D[1:]:
            ans = (ans * cnt[i - 1]) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  for i in range(1, n + 1):
    x = c[i]
    if x == 0:
      break
    r = r * pow(p, x, M) % M
    p = x; n -= p
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      r = r * pow(p, c.get(i), M) % M
      p = c[i]; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      if n < 2:
        break
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  try:
    while n > 1:
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p; i += 1
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import count

M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in count(1):
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
    r = p = i = 1
    try:
        while True:
            x = c.get(i)
            r = r * pow(p, x, M) % M
            p = x; n -= p; i += 1
    except:
        pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
import sys

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

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

countl = [0]
D = list(sorted(D))
if not check == D[0]:
    print(0)
    sys.exit()
countl = [0]
for d in D:
    if not check == d:
        check += 1
        countl.append(0)
        if not check == d:
            print(0)
            sys.exit()
    countl[-1] += 1

if not countl[0] == 1:
    print(0)
    sys.exit()

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

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  while True:
    x = c.get(i, 0)
    if x == 0:
      break
    r = r * pow(p, x, M) % M
    p = x; n -= p; i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  while True:
    x = c[i]
    if x == 0:
      break
    r = r * pow(p, x, M) % M
    p = x; n -= p; i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
    r = p = i = 1
    try:
        while True:
            x = c.get(i)
            r = r * pow(p, x, M) % M
            p = x; n -= p; i += 1
    except:
        pass
print((r, 0)[n > 1])

Submission status: Accepted

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

# bucket
lst = [[] for i in range(n)]
ans = 1
sum = 1
P = 998244353
if d[0] != 0:
    print(0)
    quit()
else:
    for i in range(n):
        if d[i] == 0 and i != 0:
            print(0)
            quit()
        lst[d[i]].append(i + 1)

    tmp = len(lst[1])
    for i in range(1, n):
        if len(lst[i]) == 0:
            if sum != n:
                print(0)
                quit()
        sum += len(lst[i])
        if i == 1:
            continue
        ans = (ans * tmp ** len(lst[i])) % P
        tmp = len(lst[i])
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
array = list(map(int, input().split()))
if array[0] != 0:
    print(0)
    exit()
array.sort()
if 1 in array and len(set(array[1:])) == 1:
    print(1)
    exit()
if not (2 in array):
    print(0)
    exit()
if 0 in array[1:]:
    print(0)
    exit()
index = array.index(2)
count = 1
count_old = array.count(1)
ans = 1
first = array[index]
for i in range(index,N-1):
    if first != array[i+1]:
        if first != array[i+1] - 1:
            print(0)
            exit()
        ans *= count_old ** count
        count_old = count
        count = 1
    else:
        count += 1
    first = array[i+1]
    ans %= 998244353
ans *= count_old ** count
ans %= 998244353
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import bisect
from itertools import groupby
 
n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
 
if li[0] != 0 or 0 in li[1:]:
    print(0)
    exit()

li.sort()
lin = []

for key, value in groupby(li):
    lin.append((key,len(list(value))))
 
point = 1
for i in range(1,len(lin)):
    if lin[i-1][0]+1 != lin[i][0]:
        print(0)
        exit()
    elif lin[i][1] == 0:
        print(0)
        exit()
    point *= (lin[i-1][1]**lin[i][1])
 
print(point%998244353)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    N = int(input())
    D = [int(i) for i in input().split()]
    if D[0] != 0:
        return print(0)
    from collections import Counter
    c = Counter(D)
    ans = 1
    for d in D[1:]:
        if d == 0:
            return print(0)
        ans *= c[d-1]
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
M = 998244353

n = int(input())
d = list(map(int, input().split()))
idx = [0]*n
ans = 1
for i in range(n):
    idx[d[i]] += 1

if not d[0] == 0 or not idx[0] == 1:
    print(0)
else:
    for i in range(1,n):
        if idx[i-1] == 0:
            if not idx[i] == 0:
                print(0)
                sys.exit()
        else:
            ans *= idx[i-1]**idx[i]%M
    else:
        print(ans%M)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
lis = [0 for i in range(10**5+100)]
ans = 1
mx = -1
for i in d:
    lis[i] += 1
    if i > mx:
        mx = i
if lis[0] != 1 or d[0] != 0:
    print(0)
else:
    for i in range(1, mx+1):
        ans *= lis[i-1]**lis[i]
    print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c, r = next(a), Counter(a), 0
if x == c[0] == 0:
    r = p = i = 1
    while c[i]:
        r = r * pow(p, c[i], M) % M
        p = c[i]; n -= p; i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c, r = next(a), Counter(a), 0
if x == c[0] == 0:
    r = p = i = 1
    while c[i]:
        r = r * pow(p, c[i], M) % M
        p = c[i]
        n -= p
        i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
    r = p = i = 1
    while c[i]:
        r = r * pow(p, c[i], M) % M
        p = c[i]
        n -= p
        i += 1
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
import sys

n = int(input())
d_list = [num for num in map(int, input().split(' '))]

# print(n)
# print(d_list)

ans = 0

d_max = max(d_list)
layer = [0] * (d_max+1)
touri = [0] * (d_max+1)

if d_list[0] != 0:
  print(0)
  sys.exit()
else:
  layer[0] = 1

for i in range(1, n):
  d = d_list[i]
  if d == 0:
    print(0)
    sys.exit()
  layer[d] += 1

touri[0] = 1
for i in range(1, len(layer)):
  count = layer[i]
  prev_count = layer[i-1]
  
  if prev_count == 1:
    touri[i] = 1
    continue
  
  if count == 1:
    touri[i] = prev_count
    continue
  
  touri[i] = prev_count ** count
    
ans = 1
for i in touri:
  ans = (ans * i) % 998244353
  
# print(layer)
# print(touri)
print(ans)

Submission status: Accepted

Solution code:
def f_b():
    n, *d = map(int, open(0).read().split())
    c = [0]*(max(d)+1)
    for i in range(n):
        c[d[i]] += 1

    a = 0 if d[0]!=0 or c[0]>1 else 1
    m = 998244353
    for i in range(1, len(c)):
        a = a*c[i-1]**c[i]%m

    print(a)

if __name__ == "__main__":
    f_b()

Submission status: Accepted

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

Submission status: Accepted

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

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

cnt = Counter(d)

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

ans = 1
for i in d:
    if i != 0:
        ans = (ans * cnt[i-1]) % 998244353
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


def main():
    m = I()
    D = LI()
    if D[0] != 0:
        return 0
    cnt = Counter(D)
    ret = 1
    for i in range(max(D) + 1):
        val = cnt[i]
        if not val:
            return 0
        else:
            if i == 0:
                if val != 1:
                    return 0
            elif i == 1:
                pre = val
            else:
                ret = pow(pre, val, mod) * ret % mod
                pre = val
    return ret


print(main())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
INF = 998244353
N = int(input())
dl = list(map(int, input().split()))
if dl[0] != 0:
    print(0)
    sys.exit()
d = defaultdict(int)

for i in range(N):
    d[dl[i]] += 1

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

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

ans = 1
for i in range(len(d) - 1, 0, -1):
    if d[i][0] - 1 == d[i - 1][0]:
        ans *= (d[i - 1][1] ** d[i][1])
        ans = ans % INF
    else:
        print(0)
        sys.exit()

print(ans)

Submission status: Accepted

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

MOD = 998244353  # type: int

def baai(n1, n2):
    return(n1**n2%MOD)

def solve(N: int, D: "List[int]"):
    cn=[0]*(N + 1)
    for i in range(N):
        cn[D[i]]+=1

    if D[0]!=0:
        print(0)
    else:
        answer=1
        bak=cn[0]
        kyo=1
        hen=1
        while True:
            cnt=cn[kyo]
            hen+=cnt
            if cnt==0:
                break
            answer=answer*baai(bak, cnt)%MOD
            bak=cnt
            kyo+=1
        if hen==N:
            print(answer%MOD)
        else:
            print(0)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
MOD = 998244353
n = int(input())
d = list(map(int, input().split()))
if d[0] != 0:
    print(0)
    exit()
c = Counter(d)
if c[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, len(c)):
    if c[i] == 0:
        print(0)
        exit()
    ans *= c[i - 1]**c[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby

M = 998244353
n = int(input())
a = map(int, input().split())
r = 0
if next(a) == 0:
    r = p = 1
    for i, (k, g) in enumerate(groupby(sorted(a)), 1):
        if k != i:
            r = 0
            break
        l = sum(1 for _ in g)
        r = r * pow(p, l, M) % M
        p = l
print(r)

Submission status: Accepted

Solution code:
import sys

a = 998244353
n = int(input())
D = list(map(int,input().split()))
if n==1 and D[0]==0:
    print(1)
    sys.exit()
elif D[0]!=0:
    print(0)
    sys.exit()
else:
    D.sort()
    if D[1]!=1:
        print(0)
        sys.exit()
    else:
        cnt = 1
        precnt = 1
        ans = 1
        for i in range(n-2):
            if D[i+2]-D[i+1]>=2:
                print(0)
                sys.exit()
            elif i+2 == n-1:
                if D[i+2]==D[i+1]:
                    cnt += 1
                    ans *= precnt**cnt
                else:
                    ans *= precnt**cnt
                    precnt = cnt
                    ans *= precnt
            elif D[i+2] == D[i+1]:
                cnt += 1
            else:
                ans *= precnt**cnt
                precnt = cnt
                cnt = 1
    print(ans%a)

Submission status: Accepted

Solution code:
from collections import Counter

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

# 条件をみたす木が存在するには D1 = 0 が必要
if D[0] != 0:
  print(0)
  exit()
# 0 == 1
ctr = Counter(D)
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:
#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def baai(n1, n2):
    return(n1**n2%MOD)

def solve(N: int, D: "List[int]"):
    cn=[0]*(N*2)
    for i in range(N):
        cn[D[i]]+=1

    if D[0]!=0:
        print(0)
    else:
        answer=1
        bak=cn[0]
        kyo=1
        hen=1
        while True:
            cnt=cn[kyo]
            hen+=cnt
            if cnt==0:
                break
            answer=answer*baai(bak, cnt)%MOD
            bak=cnt
            kyo+=1
        if hen==N:
            print(answer%MOD)
        else:
            print(0)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
D = list(map(int, input().split()))
l = [0] * N
top = max(D)
mod = 998244353
for i in range(N):
    l[D[i]] += 1
ans = 1
for i in range(1, top+1):
    if l[i] != 0:
        ans *= l[i-1] ** l[i]
    if l[i] == 0:
        print(0)
        exit()
    ans = ans % mod
if D[0] != 0:
    ans = 0
if l[0] != 1:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 998244353


n = INT()
d = MAP()

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

l = [0]*(max(d)+1)
for i in d:
    l[i]+=1

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
d_list = [int(d) for d in input().split(' ')]


def search(d_list):
    if d_list[0] != 0:
        return 0

    d_dict = defaultdict(int)
    unique_values = set()
    for d in d_list:
        d_dict[d] += 1
        unique_values.add(d)

    if d_dict.get(0) and d_dict.get(0) >= 2:
        return 0

    unique_num = len(unique_values)
    if not sum(unique_values) == unique_num * (unique_num - 1) / 2:
        return 0

    result = 1

    for v in unique_values:
        if v == 0:
            continue
        prev_node_num = d_dict.get(v-1)
        current_node_num = d_dict.get(v)

        result *= prev_node_num ** current_node_num
    return result % 998244353

print(search(d_list))

Submission status: Accepted

Solution code:
import collections
n = int(input())
d = [int(i) for i in input().split()]
 
dkaisuu = collections.Counter(d)
 
ans = 1
for i in range(1,max(d)+1): # 1,2,3
    ans *= dkaisuu[i-1]**dkaisuu[i]
if d[0] == 0 and dkaisuu[0] == 1:
    print(ans%998244353)
else:
    print(0)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

n = int(input())
li = list(map(int,input().split()))
 
ans = 1
ans_li = collections.Counter(li)

if not li[0] == 0:
    print(0)
    exit()

if not ans_li[0] == 1:
    print(0)
    exit()

for i in range(max(ans_li)+1):
    ans *= ans_li[i] ** ans_li[i+1]
    if ans_li[i] == 0:
        print(0)
        exit()
 
print(ans % 998244353)

Submission status: Accepted

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

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

ans = 1
setD = list(set(d))
# setD.sort()



if d[0] > 0:
        print(0)
else:
        c = Counter(d)
        
        # for _d in d:
        #         if _d != 0:
        #                 # print(_d - 1)
        #                 print(c[_d - 1])
        #                 # print("---------------")
        #                 ans *= c[_d - 1]

        for _d in setD:
                if _d != 0:
                        ans *= c[_d - 1] ** c[_d]

        print(ans%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
Dlist = list(map(int, input().split()))
DCounter = Counter(Dlist)
if DCounter[0] == 1 and Dlist[0] == 0:
    num = 1
    for i in range(1, max(Dlist) + 1):
        num *= DCounter[i - 1] ** DCounter[i]

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

Submission status: Accepted

Solution code:
import collections

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

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

a.sort()

c = collections.Counter(a)

ans = 1
now = 1
if a[0] != 0 or a[1]==0:
    print(0)
else:
    last = a[-1]
    for i in range(1,last+1):
        cnt = c[i]
        if cnt==0:
            ans = 0
            break
        else:
            ans *= ((now**cnt)%998244353)
            ans %= 998244353
            now = cnt
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
ans=1
x=sorted(d)
acount=1
count=1
sd=set(x)
sd=list(sd)
s=0

for i in range(1,n-1):
  if x[i]==x[i+1]:
    acount+=1
  elif x[i]!=x[i+1]:
    ans*=(count**acount)
    count=acount
    acount=1
  
if len(x)>1 and x[-1]!=x[-2]:
  ans*=count
elif len(x)>1 and x[-1]==x[-2]:
  ans*=(count**acount)

  
for i in range(len(sd)-1):
  if sd[i]+1!=sd[i+1]:
    s=1
    
if s==0:
  if d[0]==0 and x[1]!=0:
    print(ans%998244353)
  else:
    print(0)
else:
  print(0)

Submission status: Accepted

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

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

MOD = 998244353
L = [0]*(n+1)

for a in A : L[a] += 1
#print(L)

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

zerofirst = L.index(0)
for i in range(n-1,-1,-1) :
  if L[i] != 0 :
    nonzerolast = i
    break

if zerofirst < nonzerolast :
  print(0)
  exit()

ans = 1
for i in range(1,nonzerolast+1) :
  ans *= (L[i-1]) ** (L[i])
  ans %= MOD

print(ans)

#print(zerofirst, nonzerolast)

Submission status: Accepted

Solution code:
import collections
mod = 998244353

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

if d[0]!=0:
    print(0)
else:
    d.sort()
    d_max = d[-1]
    a = 1
    count = 0
    l = collections.Counter(d)
    for i in range(d_max+1):
        if l[i]==0:
            count +=1
            break

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

    if count ==1:
        print(0)
    else:
        for i in range(1,d_max+1):
            a = a*(l[i-1]**l[i])
        print(a%mod)

Submission status: Accepted

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

import math

def func(i, j, d):
    if i <= 1:
        return 1
    e = j
    b = int(math.log2(d)/math.log2(i))
    ret = 1
    while e > b:
        ret = ret*(i**b%d)
        e = e - b
    else:
        if e > 0:
            ret = ret*(i**e%d)
    return ret


def main():
    N = int(input())
    Ds = [int(d) for d in input().split()]

    if Ds[0] != 0:
        print(0)
        return

    Ds.sort()
    if Ds[1] == 0:
        print(0)
        return

    i = 1
    l = 1
    r = 1
    ans = 1
    divider = 998244353

    while i < N:
        cnt = 0
        while i < N and Ds[i] == l:
            cnt = cnt + 1
            i = i + 1
        if cnt == 0:
            print(0)
            return

        ans = ans*func(r, cnt, divider)%divider
        r = cnt
        l = l + 1
    
    print(ans)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("nikkei2019-2-qual","b",main)

Submission status: Accepted

Solution code:
N = int(input())
from collections import Counter
D = [int(i) for i in input().split()]
c = Counter(D)


if D[0] != 0:
  print(0)
  quit()
if c[0] != 1:
  print(0)
  quit()
if len(c.keys()) != max(c.keys())+1:
  print(0)
  quit()

  
res = 1
for i in range(1,1+max(c.keys())):
  res *= c[i-1]**c[i]
  res %= 998244353
print(res)

Submission status: Accepted

Solution code:
# B - Counting of Trees
import collections
N = int(input())
D = list(map(int, input().split()))

c = collections.Counter(D)
ans = 1
tmp = 1
if D[0] > 0:
    print(0)
    exit()
elif c[0] != 1:
    print(0)
    exit()
else:
    for i in range(1,max(D)+1):
        ans *= (tmp ** c[i])
        ans = ans % 998244353
        tmp = c[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a,b,c,d,i=list(map(int,input().split())),0,[],1,0
if a[0]!=0:
    print('0')
    sys.exit()
if n==1:
    print('1')
    sys.exit()
a.sort()
if a[1]==0:
    print('0')
    sys.exit()
while True:
    if a[i]==a[i+1]:
        b+=1
    else:
        c.append(b+1)
        b=0
    i+=1
    if i+1>=n:
        c.append(b+1)
        break
if len(c)-1!=max(a):
    print('0')
    sys.exit()
for i in range(len(c)-1):
    d*=c[i]**c[i+1]
print(d%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

count = Counter(d)

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


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    max_d = max(d)
    for i in range(1, max_d+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
b = collections.Counter(a)
branch = b[1]
ct = 1
for i in range(max(a)+1):
    if i == 0:
        continue
    else:
        ct *= b[i-1]**b[i]
if b[0] != 1 or a[0] != 0:
    print(0)
else:
    print(ct%998244353)