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:
def pow(x,n):
    res = 1
    for _ in range(n):
        res *= x
    return max(1,res)

def main():
    N = int(input())
    lists = [0 for i in range(N+1)]
    temp = list(map(int,input().split()))

    for elem in temp:
        lists[elem] += 1
    
    ans = 1


    if(lists[0] != 1 or temp[0] != 0):
        ans = 0
    else:
        sum = 1
        for i in range(1,N):
            ans *= pow(lists[i-1],lists[i])
            sum += lists[i]
            if(sum == N):
                break
                
            if(lists[i] == 0):
                if(sum != N):
                    ans = 0
                    break
                
    ans %= 998244353
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 998244353

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

counter = Counter(D)
# print("counter: {}".format(counter))

if D[0] != 0:
    ans = 0
else:
    ans = 1
    count = 1
    for i, item in enumerate(sorted(counter.items(), key=lambda x: x[0])):
        # print("ans: {}".format(ans))
        # print("i: {}, item: {}".format(i, item))
        if i != item[0]:
            ans = 0
            break
        if item[0] == 0 and item[1] != 1:
            ans = 0
            break

        ans *= (count ** item[1]) % MOD
        count = item[1]
print(ans % MOD)

Submission status: Accepted

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

def check():
    if D[0] != 0:
        return False
    t = sorted(list(set(D)))
    if t == list(range(len(t))):
        return True
    return False


def main():
    if check() == False:
        print(0)
        return

    C = {}
    m = 0
    for d in D:
        C[d] = C.get(d,0) + 1
        m = max(m, d)

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

    ans = 1
    for i in range(1,m+1):        
        ans *= (C[i-1] ** C[i])

    print(ans % 998244353)

main()

Submission status: Accepted

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

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

p = [0 for i in range(ma+1)]

for i in range(n):
    p[d[i]] += 1

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

Submission status: Accepted

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

mod=998244353
from collections import Counter
c=Counter(d)
if not(d[0]==0 and sorted(d)[1]!=0):
  print(0)
  exit()
d.sort()
ans=1
for i in range(1,d[-1]+1):
  if c[i]==0:
    ans*=0
  else:
    ans*=c[i-1]**c[i]
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
mod=998244353
n=int(input())
D=list(map(int,input().split()))
Count=Counter(D)
if D[0]!=0 or Count[0]!=1:print(0);exit()

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

Submission status: Accepted

Solution code:
mod = 998244353

n=int(input())

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

tree = [0]*n

for i in t:
    tree[i] += 1

if tree[0] != 1 or t[0] != 0:
    ans = 0
else:
    ans = 1
    for i in range(1,n):
        ans = (ans*pow(tree[i-1],tree[i],mod))%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def solve():
  if D[0] != 0:
    return 0
  total = 1
  max_d = max(D)
  counter = Counter(D)
  if counter[0] != 1:
    return 0
  for i in range(max_d + 1):
    if i not in counter:
      return 0
    if i > 1:
      total *= (counter[i - 1] ** counter[i] % P)
      total %= P
  return total

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] > 0 or a.count(0) > 1:
  print(0)
  exit()
  
a = sorted(a)
dp = [0]*(n+1)
dp[0] = 1
count_list = [0]*n
count_list[0] = 1
for i in range(1, n):
  count_list[a[i]] += 1
for i in range(1, a[n-1]+1):
  dp[i] = dp[i-1] * count_list[i-1] ** count_list[i] % 998244353
print(dp[a[n-1]])

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
d=list(map(int,input().split()))
mod=998244353
if d[0]!=0:
      print(0)
      exit()
dd=defaultdict(lambda:0)
for di in d:
      dd[di]+=1
if dd[0]>1:
      print(0)
      exit()
ans=1
for i in set(dd.keys()):
      if i==0:
            continue
      ans*=(dd[i-1]**dd[i])%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    D=[int(_) for _ in input().split()]
    dc=Counter(D)
    mod,ans=998244353,1
    if D[0]!=0 or dc[0]!=1:
        print(0)
        sys.exit()
    for i,_ in enumerate(list(dc.items())):
        if i>1:
            ans*=dc[i-1]**dc[i]%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b
# まず、本当に木を構築するモノではないだろう
from collections import Counter
n = int(input())
nums = [int(i) for i in input().split()]
mod = 998244353
MAX = max(nums)

c = Counter(nums)
if nums[0] != 0 or nums.count(0) != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, MAX + 1):
        ans = ans * pow(c.get(i - 1, 0), c.get(i, 0), mod) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
    print(0)
    exit()
del d[0]
for i in range(n-1):
    if d[i]==0:
        print(0)
        exit()
dcnt=[0]*(n)
for i in range(n-1):
    dcnt[d[i]]+=1
for j in range(n-1,-1,-1):
    if dcnt[j]==0:
        del dcnt[j]
    else:
        break
if len(dcnt)==0:
    print(0)
    exit()
dcnt[0]=1
sum=1
for i in range(1,len(dcnt)):
    sum*=pow(dcnt[i-1],dcnt[i])
    sum%=998244353
print(sum)

Submission status: Accepted

Solution code:
import sys
n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
    print(0)
    sys.exit(0)
if n==1:
    print(1)
    sys.exit(0)
for i in range(1,n):
    if d[i]==0:
        print(0)
        sys.exit(0)
dist=[0]*(n) 
for i in range(1,n):
    dist[d[i]]+=1
if dist[1]==0:
    print(0)
    sys.exit(0)
ans=1
mod=998244353
bef=dist[1]
total=dist[1]+1
for i in range(2,n):
    for j in range(dist[i]):
        ans=ans*bef
        ans=ans%mod
    total+=dist[i]
    bef=dist[i]
    if total==n:
        break
    if ans==0:
        break
print(ans)
#print(dist)

Submission status: Accepted

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

count_dict = {}
for i in range(n):
    count_dict[i] = 0
for val in d_l:
    count_dict[val] += 1

if d_l[0] != 0 or count_dict[0] != 1:
    ans = 0
else:
    ans = 1

for i in range(1,n):
    ans = (ans*(count_dict[i-1]**count_dict[i])) %998244353
    if ans == 0:
        break

print(ans)

Submission status: Accepted

Solution code:
from sys import exit

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

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

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

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

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

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()))

    tree = [0 for _ in range(max(D) + 1)]
    for i in range(n):
        idx = D[i]
        tree[idx] += 1

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

    res = 1
    for i in range(len(tree) - 1):
        res *= pow(tree[i], tree[i + 1], mod)

    print(res % mod)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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


def main():
    N = INT()
    D = LIST()
    if D[0] > 0 or D.count(0) > 1:
        print(0)
        exit()

    D.sort()
    ct = [1] * (max(D)+1)
    for i in range(N):
        if D[i] - D[i-1] > 1:
            print(0)
            exit()
        elif D[i] - D[i-1] == 0:
            ct[D[i]] += 1
    ans = 1
    for i in range(1, max(D)+1):
        ans *= pow(ct[i-1], ct[i], 998244353)
        ans %= 998244353

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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
from fractions import gcd
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 = 998244353

N = INT()
D = LIST()

cnt_D = Counter(D)
if D[0] != 0 or cnt_D[0] >= 2:
	print(0)
	exit()

ans = 1

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

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 998244353
 
    N = II()
    D = LMIIS()
    num_D = [0]*N
    for d in D:
        num_D[d] += 1
    if D[0] != 0 or num_D[0] != 1:
        print(0)
        return
    ans = 1
    prev = 1
    dbg(num_D)
    for i,v in enumerate(num_D):
        if v == 0:
            if N-i != num_D.count(0):
                print(0)
                return
            break
        ans *= pow(prev,v,MOD)
        ans %= MOD
        prev = v
    print(ans)


    

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
d=[int(j) for j in input().split()]
if d[0]!=0:
    print(0)
    exit()
mod=998244353
import collections
c=collections.Counter(d)
l=c.most_common()
l.sort()
ans=1
tmp=0
for i in range(len(l)):
    if i==0:
        if l[i][1]!=1:
            print(0)
            exit()
        tmp=1
        continue
    if l[i][0]!=i:
        print(0)
        exit()
    ans=(ans*pow(tmp,l[i][1],mod))%mod
    tmp=l[i][1]
print(ans)

Submission status: Accepted

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

#以下が an mod p を求めるソースコードです.
def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

bucket = [0] * (max(D) + 1)
for dist in D:
    bucket[dist] += 1
# print(bucket)

if bucket[0] != 1 or D[0] != 0:
    print(0)
else:
    ans = 1
    for i in range(len(bucket) - 1):
        ans = (ans * power_func(bucket[i], bucket[i + 1], MOD)) % MOD
    print(ans)

Submission status: Accepted

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

dist = [0] * 10**5
max_d = 0
for d in d_list:
    dist[d] += 1
    max_d = max(max_d, d)

MOD = 998244353
if d_list[0] != 0:
    print(0)
    exit()
elif dist[0]>1:
    print(0)
    exit()

ans = 1
for i in range(max_d):
    if dist[i] == 0 or dist[i+1] ==0:
        print(0)
        exit()
    ans *= (dist[i]**dist[i+1])
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


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

    # cnt[k] = v ... 深さkのノード数
    cnt = {}
    max_depth = 0
    for d in D:
        max_depth = max(max_depth, d)
        if d not in cnt:
            cnt[d] = 1
        else:
            cnt[d] += 1

    # 頂点1との距離が0になるノードは1つしか存在しない
    if D[0] != 0:
        print(0)
        exit(0)
    elif cnt[0] > 1:
        print(0)
        exit(0)

    ans = 1
    MOD = 998244353
    for i in range(0, max_depth):
        if (i not in cnt) or (i + 1 not in cnt):
            ans = 0
            break
        ans *= cnt[i] ** cnt[i + 1]
        ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)
MOD = 998244353


def main():
    N = int(input())
    D = list(map(int, input().split()))
    C = Counter(D)
    if D[0] != 0:
        print(0)
    elif C[0] > 1:
        print(0)
    else:
        ans = 1
        key = list(C.keys())
        key.sort()
        l = len(key)
        for i in range(1, l):
            if key[i - 1] + 1 != key[i]:
                a = 0
            else:
                a = C[key[i - 1]] ** C[key[i]]
            ans *= a
            ans %= MOD
            if ans == 0:
                break
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
MOD = 998244353

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

aa = Counter(a)
ma = max(aa)

def po(x,n):
    k = 1
    for i in range(n):
        k = k*x % MOD
    return k

if aa[0] != 1 or a[0] != 0:
    print(0)
    sys.exit()
    
ans = 1
for i in range(ma):
    c,d = aa[i],aa[i+1]
    if c == 0 or d == 0:
        print(0)
        sys.exit()
    else:
        ans = ans * po(c,d) % MOD
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
mod = 998244353
if a[0] !=0:
    ans = 0

cnt = [0]*n
for i in range(n):
    cnt[a[i]] += 1
for i in range(1,n):
    ans *= cnt[a[i]-1]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

depth = defaultdict(int)
for d in D:
    depth[d] += 1

# つながらない
if D[0] != 0 or depth[0] != 1:
    print(0)
    exit()

mod = 998244353
ans = 1
for d in range(1, max(D) + 1):
    ans *= pow(depth[d - 1], depth[d], mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter

N = int(input())
D = list(map(int, input().split()))
c = Counter(D)
M = max(c.keys())

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

mod = 998244353
depth = 1
ans = 1
while depth <= M:
    ans *= pow(c[depth - 1], c[depth], mod)
    ans %= mod
    depth += 1
print(ans)

Submission status: Accepted

Solution code:
import collections
N  = int (input())
nums = list(map(int,input().split(" ")))
MOD = 998244353
di = collections.defaultdict(lambda :0)
for num in nums:
    di[num] += 1


ans = 1 if nums[0] == 0 else 1
ans = 0 if 0 in nums[1:]  else 1
bottom = min(nums)
top= max(nums)
for d in range(1,top + 1):
    ans *= pow(di[d - 1] ,di[d ],MOD)


print(ans % MOD)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
D = LIST()

mod = 998244353
c = Counter(D)
v = max(D)

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

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
N = int(input())
D = list(map(int, input().split()))
assert len(D) == N
dcnt = Counter(D)

def solve():
    if D[0] != 0:
        return 0
    D.sort()
    if N > 1 and D[1] != 1:
        return 0
    i = 1
    res = 1
    leaf = 1
    k = 0
    while i < N:
        if D[i] != k + 1:
            return 0
        k += 1
        c = dcnt[k]
        res *= pow(leaf, c, M)
        leaf = c
        i += c
    return res % M

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

P = 998244353


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

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

    if not ((D[0] == 0) and (cnt[0] == 1) and (0 not in cnt)):
        print(0)
    else:
        ans = 1
        for i in range(len(cnt) - 1):
            ans *= pow(cnt[i], cnt[i + 1], P)  # a**b mod p
            ans %= P
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ans = 1
A = [0]*(max(D)+1)
for i in range(N):
  A[D[i]] += 1
if D[0] != 0 or not all(D[1:]) or not all(A):
  print(0)
  exit()
for i in range(1, max(D)+1):
  ans = ans * pow(A[i-1], A[i], mod) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ans = 1
A = [0]*(max(D)+1)
for i in range(N):
  A[D[i]] += 1
#if D[0] != 0 or not all(D[1:]) or not all(A):
#  print(0)
#  exit()
if D[0] != 0 or not all(D[1:]):
  print(0)
  exit()
for i in range(1, max(D)+1):
#  print(A[i])
  if A[i] == 0:
    print(0)
    exit()
  ans = ans * pow(A[i-1], A[i], mod) % mod
print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int, input().split()))
mod = 998244353
ans = 1
A = [0]*(max(D)+1)
for i in range(N):
  A[D[i]] += 1
if D[0] != 0 or not all(D[1:]) or not all(A):
  print(0)
  exit()
if D[0] != 0:
  print(0)
  exit()
for i in range(1, max(D)+1):
#  if A[i] == 0:
#    print(0)
#    exit()
  ans = ans * pow(A[i-1], A[i], mod) % mod
print(ans % mod)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 998244353

from collections import Counter, deque

def solve(N,D):
    if D[0]!=0:
        return 0
    c = Counter(D)
    if c[0]>1:
        return 0
    ans = 1
    m = max(D)
    for i in range(1,m):
        # if c[i]==0:
        #     ans = 0
        #     continue
        ans *= pow(c[i],c[i+1],mod)
        ans %= mod
    return ans

print(solve(N,D))

Submission status: Accepted

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

mod = 998244353

from collections import Counter, deque

def solve(N,D):
    if D[0]!=0:
        return 0
    c = Counter(D)
    if c[0]>1:
        return 0
    ans = 1
    m = max(D)
    for i in range(1,m):
        if c[i]==0:
            ans = 0
            continue
        ans *= pow(c[i],c[i+1],mod)
        ans %= mod
    return ans

print(solve(N,D))

Submission status: Accepted

Solution code:
from collections import Counter

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

if D[0] != 0:
    print(0)
else:
    c = Counter(D)
    c = sorted(c.items(), key=lambda x: x[0])
    ans = 1
    prev = 1
    dist = [False] * (N + 1)
    dist[0] = True
    for k, v in c:
        if k == 0:
            if v > 1:
                print(0)
                break
        else:
            if dist[k - 1] is not True:
                print(0)
                break
            dist[k] = True
            ans *= prev ** v
            ans %= MOD
            prev = v
    else:
        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)
cnt = 1
M = max(c.keys())
ans = 1
if D[0]!=0 or c[0]!=1:
  print(0)
  import sys
  sys.exit()
while cnt<=M:
  ans *= c[cnt-1]**c[cnt]
  ans %= MOD
  cnt += 1
print(ans)

Submission status: Accepted

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



#%%
d_cnt =Counter(d)
d_cnt = dict(d_cnt)

d_cnt_keys = list(d_cnt.keys())
d_cnt_keys.sort()

if d[0] != 0 or d_cnt[0] != 1 or len(d_cnt_keys)!= d_cnt_keys[-1]+1:
    print(0)
    exit()

#%%

ans = 1
p = 998244353
for key in d_cnt_keys:
    if key == 0:
        continue
    ans =ans*pow(d_cnt[key-1], d_cnt[key],p)%p
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()

m = max(d)

cnt = collections.Counter(d)
if cnt[0] != 1:
    print(0)
    exit()

ans = 1

for i in range(1, m + 1):
    if cnt[i] == 0:
        print(0)
        exit()
    ans *= pow(cnt[i - 1], cnt[i], mod)
    ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(1, max_dist + 1):
    ans *= (count[i - 1] ** count[i]) % mod
    ans %= mod

if count[0] > 1 or D[0] != 0:
    ans = 0

print(ans % 998244353)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter

n = int(readline())
d = list(map(int, readline().split()))
counter = Counter(d)
mod = 998244353
ans = 1
if d[0] != 0 or counter[0] != 1:
    print(0)
    exit()
for i in range(1, max(d) + 1):
    ans *= pow(counter[i - 1], counter[i], mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import collections
N=int(input())
D=list(map(int,input().split()))
l=[]
c=collections.Counter(D)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
p=998244353
cnt=1
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#print(l)
if (c[0]==1)and(D[0]==0):
    for i in range(N-1):
        cnt=cnt*pow(c[i],c[i+1],p)
    print(cnt%p)
else:
    print("0")

Submission status: Accepted

Solution code:
import collections
N=int(input())
D=list(map(int,input().split()))
l=[]
c=collections.Counter(D)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
p=998244353
cnt=1
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#print(l)
if (c[0]==1)and(D[0]==0):
    for i in range(N-1):
        cnt=(cnt*pow(c[i],c[i+1],p))%p
    print(cnt%p)
else:
    print("0")

Submission status: Accepted

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

N = int(input().split()[0])
d_list = list(map(int, input().split()))
counter = collections.Counter(d_list)
max_d = max(counter.keys())
w = 0
mod = 998244353

if d_list[0] != 0 or counter[0] >= 2:
    w = 0
else:
    for d in range(1, max_d + 1):
        if d not in counter.keys():
            w = 0
            break
        if d == 1:
            w += 1
            continue
        x = counter[d - 1] ** counter[d]  # D=iとなるルートのパターン数
        w = (w % mod) * x
w = w % mod
ans = w
print(ans)

Submission status: Accepted

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

cnt=1
#print(b)
#print(b[1:])
for v1,v2 in zip(b,b[1:]):
    #print(v1)
    #print(v2)
    cnt *= v1**v2 % MOD
print(cnt%MOD)

Submission status: Accepted

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

branchs = [0] * N
MOD = 998244353

for d in D_list:
    branchs[d] += 1

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

cnt = 1
for v1,v2 in zip(branchs, branchs[1:]):
    cnt *= v1**v2 % MOD
    
print(cnt%MOD)

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))
mod=998244353
ans=1
count=[0 for i in range(0,N)]
for i in range(0,N):
    count[D[i]]+=1

able=True
if D[0]!=0 or count[0]!=1:
    able=False
for i in range(0,N-1):
    if count[i]==0 and count[i+1]!=0:
        able=False

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*D, = map(int, input().split())
mod = 998244353
c = Counter(D)
v = max(D)

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*D, = map(int, input().split())
mod = 998244353
c = Counter(D)
v = max(D)

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

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
if l[0]:print(0);exit()
mod=998244353
k=[0]*n
for i in l:k[i]+=1
if k[0]!=1:print(0);exit()
ans=1
for i,s in zip(k,k[1:]):ans*=pow(i,s,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(tree)
if tree[0] != 0 or 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)
            exit()
        else:
            ans *= ( a**t )
            a = t
    print(ans%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
inputs = open(0).readlines()

n = int(inputs[0])
*D, = map(int, inputs[1].split())
mod = 998244353

nbs = [0] * (max(D)+1)
for k, v in Counter(D).items():
    nbs[k] = v

if D[0] != 0 or nbs[0] != 1:
    print(0)
else:
    ans = 1
    for n0, n1 in zip(nbs, nbs[1:]):
        ans = ans * pow(n0, n1, mod) % mod
    print(ans)

Submission status: Accepted

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

MOD = 998244353  # type: int


def solve(N: int, D: "List[int]"):
    from collections import Counter
    c = Counter(D)

    x = sorted(list(set(D)))
    if any([0 >= i for i in D[1:]]):
        print(0)
        exit()

    if D[0] != 0 or len(x) <= 1 or max(x) - min(x) + 1 != len(x):
        print(0)
        exit()

    ans = 1
    for i in range(2, N):
        if c[i - 1] >= 2:
            ans *= pow(c[i - 1], c[i]) % MOD

    print(ans % MOD)

    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:
def main():
    length = int(input())
    distance = list(map(int, input().split()))
    count_distance = {}
    for d in distance:
        if d in count_distance:
            count_distance[d] += 1
        else:
            count_distance[d] = 1
    count_distance = sorted(count_distance.items(), key=lambda x: x[0])
    answer = 0
    mod = 998244353
    if distance[0] == 0 and count_distance[0][1] == 1:
        answer = 1
        for i in range(1, len(count_distance)):
            if count_distance[i][0] == count_distance[i - 1][0] + 1:
                answer = (answer * pow(count_distance[i - 1][1], count_distance[i][1], mod)) % mod
            else:
                answer = 0
                break
    print(answer)


if __name__ == '__main__':
    main()