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_array = [int(x) for x in input().split()]
counter = {x: 0 for x in range(-1, 10 ** 5 + 1)}
for i in d_array:
    counter[i] += 1
MOD = 998244353
if d_array[0] != 0 or counter[0] != 1:
    print(0)
    exit()
ans = 1
for num in set(d_array):
    if num == 0:
        continue
    if counter[num-1] == 0:
        print(0)
        exit()
    ans *= (counter[num-1])**counter[num]
    ans = ans % MOD
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())

lis = [0] * (10 ** 5 + 10)

D = list(map(int,input().split()))
maxi = 0

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

for i in D:
    maxi = max(maxi,i)
    lis[i] += 1

ans = 1
for i in range(maxi + 1):

    if i == 0 and lis[i] != 1:
        ans = 0
        print (0)
        sys.exit()
    elif i != 0:
        #print (ans,lis[i-1],lis[i])
        ans = ans * ( lis[i-1] ** lis[i] ) 
        ans %= 998244353

#print (lis)
print (ans % 998244353)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    C = [0] * (max(D) + 1)
    for d in D:
        C[d] += 1
    # print(C)
    
    if D[0] != 0 or C[0] >= 2:
        print(0)
        return
    
    ans = 1
    for i in range(len(C) -1):
        for _ in range(C[i+1]):
            ans *= C[i]
            ans %= 998244353
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

M = 998244353
n = int(input())
d = list(map(int, input().split()))
counter = Counter(d)

if d[0] != 0 or counter[0] != 1:
    ans = 0
else:
    ans = counter[0]
    for i in range(1, max(d) + 1):
        if counter[i] == 0:
            ans = 0
            break
        m, n = counter[i - 1], counter[i]
        c = m ** n
        ans *= c

print(ans % M)

Submission status: Accepted

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    n = int(input())
    d = list(map(int, input().split()))
    # 各距離の頂点数を求める
    c = collections.Counter(d)
    ans = 1
    tmp = -1
    # 頂点1のみが0である必要がある
    if d[0] != 0 or c[0] > 1:
        print(0)
        exit()
    # 個数の計算
    for i in range(2, n):
        if i - 1 in c.keys():
            ans *= c[i - 1] ** c[i]
            ans %= 998244353
        else:
            tmp = i
            break
    # 距離が連番になっていなければ到達不可能
    if tmp >= 0:
        for j in range(tmp, n):
            if j in c.keys():
                print(0)
                exit()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
d = defaultdict(int)
m = 0
for i in a:
    d[i] += 1
    m = max(m,i)
res = 1
tmp = 1
for i in range(m+1):
    if i == 0:
        if d[i] != 1 or a[0] != 0:
            print(0)
            quit()
        continue
    if d[i] == 0:
        res = 0
        break
    if i == 1:
        tmp = d[i]
        continue
    res *= (tmp ** d[i] )%998244353
    tmp = d[i]
print(res%998244353)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
D = [int(x) for x in stdin.readline().rstrip().split()]
mod = 998244353
ans = 1
if N == 1 and D[0] == 0:
    print(1)
elif len(set(D))==1:
    print(0)
elif D.count(0) != 1:
    print(0)
elif D[0] != 0:
    print(0)
else:
    tmp = 1
    cnt = Counter(D)
    #print(cnt)
    flag = True
    for i in range(1,max(D)+1):
        #print(cnt[i],tmp)
        if i != 1 and cnt[i] != tmp:
            flag = False
        c = (tmp**cnt[i]) % mod
        ans *= c % mod
        tmp = cnt[i]
        ans = ans % mod
    if flag:
        print(1)
    else:
        print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
L = [int(i) for i in input().split()]
LL = [0 for i in range(pow(10,5)+1)]
 
for i in range(n):
  LL[L[i]] += 1
  
MOD = 998244353
out = 1
maximum = max(L)
for i in range(maximum):
  out = (out * pow(LL[i], LL[i+1], MOD)) % MOD
 
if L[0] != 0 or LL[0] != 1:
  out = 0

for i in range(maximum):
  if L[i+1] == 0:
    out = 0
  
print(out)

Submission status: Accepted

Solution code:
import collections
import sys

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

cnt = collections.Counter(d)

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

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

for i in range(1,max(d)+1):
    p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)

Submission status: Accepted

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

list2 = [0]*(max(list1)+1)

for i in range(len(list1)):
    list2[list1[i]] += 1

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

#根が2個あるならexit
if list2[0] != 1:
    print(0)
    exit()
#枝が繋がっていないならexit
if 0 in list2:
    print(0)
    exit()

count = 1
for i in range(1,len(list2)):
    count *= list2[i-1]**list2[i]
    count %= 998244353

print(count)

Submission status: Accepted

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

if d[0] != 0:
    print(0)
    exit()
count = [0 for _ in range(max_d+1)]
for i in range(n):
    count[d[i]] += 1
if count[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(max_d):
    n = count[i]
    m = count[i+1]
    ans *= n**m%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def calc(n, D):
    if D[0] != 0:
        return 0
    count = [0 for i in range(n)]
    for i in D:
        count[i] = count[i] + 1
    if count[0] != 1:
        return 0
    #for i in count:
    #    print("count",i)
    tmp = 1
    sum = 0
    for i in range(n-1):
    #    print(count[i],count[i+1])
        sum = sum + count[i]
        if sum == n:
            break
        if count[i] == 0:
            tmp = 0
            break
        tmp = tmp * (count[i]**count[i+1])
    return tmp

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

print(calc(n,D) % 998244353)

Submission status: Accepted

Solution code:
import collections

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

d.sort()

c = collections.Counter(d)
if c[0] != 1:
    print('0')
else:
    ans = 1
    k = list(c.keys())
    v = list(c.values())
    for i in range(1, len(v)):
        if k[i]-1 != k[i-1]:
            ans *= 0
        ans *= (v[i-1]**v[i]) % MOD
    print(ans % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
d = [int(i) for i in input().split()]
c = Counter(d)

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

cnt = 1
for i in range(1,max(d)+1):
    cnt *= pow(c[i-1],c[i])

print(cnt % MOD)

Submission status: Accepted

Solution code:
from sys import stdin
import collections
def main():
    n = int(stdin.readline().rstrip())
    D = [int(i) for i in input().split()]
    hash = collections.Counter(D)
    if(hash[0] != 1 or D[0] != 0):
        print(0)
        return
    count = hash[0]
    for i in range(1, max(D)+1):
        count *= hash[i-1] ** hash[i]
    print(count%998244353)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys

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

cnt = collections.Counter(d)

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

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

for i in range(1,max(d)+1):
    if cnt[i] == 0:
        print(0)
        sys.exit(0)  
    else:
        p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)

Submission status: Accepted

Solution code:
from sys import stdin
import collections
def main():
    n = int(stdin.readline().rstrip())
    D = [int(i) for i in input().split()]
    hash = collections.Counter(D)
    count = hash[0]
    if(count != 1 or D[0] != 0):
        print(0)
        return
    for i in range(1, max(D)+1):
        count *= hash[i-1] ** hash[i]
    print(count%998244353)
    
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
# print(*l)
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:
N = int(input())
D = list(map(int,input().split()))
_mod = 998244353

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

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

ans = 0

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

cnt = 0
for i in range(N):
  cnt += a[i]
  if i == 0:
    ans = 1
  else:
    if a[i] == 0:
      if cnt == N:
        break
      else:
        ans = 0
    else:
      temp = a[i-1] ** a[i]
      ans = (ans * temp ) % _mod

print(ans)

Submission status: Accepted

Solution code:
import math

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

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

dict = {}

for i in range(len(D)):
    if D[i] not in dict:
        dict[D[i]] = 1
    else:
        dict[D[i]] += 1

for i in range(max(D)):
    if i not in dict:
        dict[i] = 0
    
for key in dict:
    if key == 0:
        if dict[key] != 1:
            print(0)
            exit()       
    if dict[key] == 0:
        print(0)
        exit()
sum = 1
n = 0

#dict = list(sorted(dict.items(), key=lambda x:x[0]))
dict_dm = sorted(dict)
#print(dict)
#print(dict_dm)
flg = 0
for i in range(len(dict_dm)):
    if i == 1:
        #print("check2")
        n = dict[i]
    elif i >=1:
        #print("check1")
        sum = (sum * n**dict[i])%998244353
        n = dict[i]

print(sum%998244353)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
D=many_int()

num=998244353


dicts={i:0 for i in range(N)}
for d in D:
    if d in dicts:
        dicts[d] += 1
    else:
        dicts[d] = 1

sums = 1
keys = sorted(list(dicts.keys()))

test = [i for i in range(len(keys))]
flg=False
for t,k in zip(test,keys):
    if t!=k:
        flg=True

if keys[0]!=0 or D[0]!=0:
    flg=True
else:
    if dicts[0]!=1:
        flg=True
        
if flg:
    sums=0

for i in range(len(keys)-1):
    if i >= 1:
        for j in range(dicts[keys[i+1]]):
            sums *= (dicts[keys[i]])
            sums = sums%num
print(sums)

Submission status: Accepted

Solution code:
from collections import Counter

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

mem = Counter(d)

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

count = 1
for i in range(max(d)):
  count = count * mem[i] ** mem[i+1]
  count = count % 998244353

print(count)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
db = [0] * (max(d)+1)
MOD = 998244353

#距離iの頂点の数をdb[i]に保存
for i in range(n):
    db[d[i]] += 1

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

ans = 1

for i in range(len(db)-1):
    ans *= db[i]**db[i+1]%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


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

    distance = [0] * (max(d) + 1)

    for _d in d:
        distance[_d] += 1

    if d[0] != 0 or distance[0] != 1:
        print(0)
        return

    ans = 1
    for i in range(1, len(distance)):
        n = distance[i-1]
        r = distance[i]
        ans = ans * n ** r
        ans = ans % MOD
        # print(ans)

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
 
n = int(input())
d = list(map(int,input().split()))
MOD = 998244353
#頂点1が0でないとだめ
if d[0]!=0:
  print(0)
  exit()
  
#同じ長さの位置に何個頂点があるか
cnt = dict(collections.Counter(d))
#頂点1だけが0じゃないとだめ
if cnt[0]==1:
  m = max(cnt)
  #一番大きい数字までにちゃんとすべての数字が揃ってないとだめ
  for i in range(m):
    if i not in cnt:
      print(0)
      exit()
  ans = 1
  for i in range(m):
    val_1 = cnt[i]
    val_2 = cnt[i+1]
    ans *= (val_1**val_2)%MOD
 
  print(ans%MOD)
else:
  print(0)

Submission status: Accepted

Solution code:
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353


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

    distance = [0] * (N + 1)

    for _d in d:
        distance[_d] += 1

    if d[0] != 0 or distance[0] != 1:
        print(0)
        return

    ans = 1
    for i in range(1, (N + 1)):
        n = distance[i-1]
        r = distance[i]
        ans = ans * n ** r
        ans = ans % MOD
        # print(ans)

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)

Submission status: Accepted

Solution code:
# coding: utf-8
import collections

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


for i in range(m):
    ans*=c[i]**c[i+1]
    ans = ans%998244353

if c[0]!=1:
    ans=0
if d[0] != 0:
    ans = 0

# print(c)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    n = int(input())
    d = list(map(int, input().split()))
    c = collections.Counter(d)
    ans = 1
    tmp = -1
    if d[0] != 0 or c[0] > 1:
        print(0)
        exit()
    for i in range(2, n):
        if i - 1 in c.keys():
            ans *= c[i - 1] ** c[i]
            ans %= 998244353
        else:
            tmp = i
            break
    if tmp >= 0:
        for j in range(tmp, n):
            if j in c.keys():
                print(0)
                exit()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
from collections import Counter
 
mod = 998244353
c = Counter(D)
max_D = max(D)
if c[0]!=1:
  print(0)
  
elif D[0]!=0:
  print(0)
  
elif max_D<=1:
  print(1)
  
else:
  answer=1
  for i in range(2,max_D+1):
    c_i2 = c[i]
    c_i1=c[i-1]
    answer = ((answer % mod) * ((c_i1**c_i2) % mod)) % mod
    
  print(answer%998244353)

Submission status: Accepted

Solution code:
n = int(input())
mod = 998244353
c=0
a = list(map(int,input().split()))
if a[0] != 0:
    print(0)
else:
    a.sort()
    mem = {}
    mem['-1']=1
    count = 1

    for v in a:
        need = v - 1
        if str(need) in mem:
            count *= mem.get(str(need))
            count %= mod
        else:
            count = 0
            break
        if str(v) in mem:
            mem[str(v)] = mem.get(str(v)) + 1
        else:
            mem[str(v)] = 1
    if '0' in mem and mem.get('0') > 1:
        print(0)
    else:
        print(count % mod)
    # print(mem)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# from operator import mul
# from functools import reduce
# import itertools

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# def combinations_with_replacement_count(n, r):
#     return combinations_count(n + r - 1, r)

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

def get_answer(len_target_list, target_list):
    pattern_dic = {}
    ans = 1
    if D_list[0] != 0:
        return 0
    else:
        for i in range(1, N):
            if D_list[i] == 0:
                return 0
            pattern_dic[D_list[i]] = pattern_dic.get(D_list[i], 0) + 1
        if 1 in pattern_dic:
            before_num = pattern_dic[1]
            for j in range(2, max(pattern_dic.keys()) + 1):
                if j in pattern_dic:
                    ans = (ans * (before_num ** pattern_dic[j])) % 998244353
                    before_num = pattern_dic[j]
                else:
                    return 0
            else:
                return ans
        else:
            return 0        

print(get_answer(N, D_list))

Submission status: Accepted

Solution code:
import collections
n=int(input())
d=list(map(int, input().split()))
num=collections.Counter(d)
"""d=sorted(list(map(int, input().split())))
num=[0]*(max(d)+1)
num_=0
count=0
j=0
for i in range(len(d)):
    if d[i]==j:
        num[j]+=1
    elif d[i]==j+1:
        num[j+1]+=1
        j+=1
    else:
        j+=1"""
#print(num)
ans=1
for i in range(1, max(d)+1):
    #print(num[i-1]**num[i])
    #ans = ans * pow(num[i-1], num[i], 998244353)%998244353
    ans*=num[i-1]**num[i]

if d[0]!=0 or d.count(0)!=1:
    print(0)
else:
    print(ans%998244353)

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

mod = 998244353

set_d = set(d)
list_d = list(set_d)
list_d.sort()
dict_d = Counter(d)

if dict_d[0] == 1:
    pass
else:
    print(0)
    exit()

ans = 1
cnt = 1
temp = -1
check = 1

for i in list_d:

    if i != temp + 1:
        print(0)
        exit()
        
    temp = i
    cnt = dict_d[i]
    ans = (ans * (check**cnt))%mod
    check = cnt
    
print(ans)

Submission status: Accepted

Solution code:

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

#距離iの頂点の数をdb[i]に保存
for i in range(n):
    db[d[i]] += 1

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

ans = 1

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

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()
num = max(a)
aset = [0 for i in range(num+1)]

for i in a:
  aset[i] += 1
#print(aset)
if aset[0] == 1 and a[0] == 0:
  ans = 1
  for i in range(1,num+1):
    ans *= (aset[i-1]**aset[i]) %mod
    #print(aset[i-1], aset[i])
  print(ans %mod)

else:
  print(0)

"""
10
0 1 1 1 1 1 1 3 2 1
"""

Submission status: Accepted

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

ct = Counter(Ds)
M = max(ct)
if Ds[0] != 0 or ct[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, M+1):
    ans *= pow(ct[i-1], ct[i], MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None


if D.count(0)==1 and D[0]==0:

    L=[0]*(max(D)+1)

    for i in range(len(D)):
        L[D[i]]+=1

    mul=1

    for i in range(len(L)-1):
        mul*=L[i]**L[i+1]%998244353
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def print_ans(N, input_line):
    """Test Case
    >>> print_ans(4, "0 1 1 2")
    2
    >>> print_ans(4, "1 1 1 1")
    0
    >>> print_ans(7, "0 3 2 1 2 2 1")
    24
    """
    ar = list(map(int,input_line.split()))
    ngflg = False
    if ar[0] != 0:
        ngflg = True
    k = max(ar)
    tmp_ar = [0] * (k + 1)
    for i in range(1,N):
        tmp_ar[ar[i]] += 1
    if tmp_ar[0] > 0:
        ngflg = True
    if ngflg:
        print("0")
    else:
        ans = 1
        for j in range(2, k + 1):
            ans *=  tmp_ar[j - 1] ** tmp_ar[j]
        print(ans % 998244353)

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = input().rstrip()
    print_ans(N, ar)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
D = list(map(int, input().split()))
MOD = 998244353
C = Counter(D)
ans = 0
if C[0] != 1 or D[0] != 0:
    print(ans)
else:
    for i, n in C.items():
        if i == 0:
            ans = 1
            continue
        ans *= pow(C[i-1], n, MOD)
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int, input().split()))
box = [0 for x in range(max(li)+1)]
for i in li:
    box[i] += 1
count = 1

if len(box) > 2:
    for i in range(1, len(box)-1):
        count *= box[i] ** box[i+1]
        count %= 998244353
else:
    count = 1
    
if box[0] != 1 or li[0] != 0:
    count = 0

print(count % 998244353)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_dic = collections.Counter(d_l)
    if count_dic[0] != 1:
        print(0)
        sys.exit()
    
    for i in range(2, d_max+1):
        ans *= count_dic[i-1] ** count_dic[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#from itertools import groupby
import numpy as np
def print_ans(N, input_line):
    """Test Case
    >>> print_ans(4, "0 1 1 2")
    2
    >>> print_ans(4, "1 1 1 1")
    0
    >>> print_ans(7, "0 3 2 1 2 2 1")
    24
    """
    ar = list(map(int,input_line.split()))
    ngflg = False
    if ar[0] != 0:
        ngflg = True
    k = max(ar)
    tmp_ar = [0] * (k + 1)
    for i in range(1,N):
        tmp_ar[ar[i]] += 1
    if tmp_ar[0] > 0:
        ngflg = True
    if ngflg:
        print("0")
    else:
        ans = 1
        for j in range(2, k + 1):
            ans *=  tmp_ar[j - 1] ** tmp_ar[j]

        print(ans % 998244353)
        # print(np.prod(ans_ar) % 998244353)

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = input().rstrip()
    print_ans(N, ar)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 998244353

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

cnt = defaultdict(int)
m = 0
for i in range(n):
    cnt[d[i]] += 1
    m = max(d[i], m)

if d[0] != 0 or cnt[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, m + 1):
        ans *= cnt[i - 1]**cnt[i]
        ans %= MOD

print(ans)

Submission status: Accepted

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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

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

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

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

print(result % 998244353)

Submission status: Accepted

Solution code:
MOD = 998244353
N = int(input())
D = list(map(int,input().split()))
ans = [0]*N
for i in D:
    ans[i] += 1
ret = 1
for i in range(1,max(D)+1):
    ret *= (ans[i-1] ** ans[i])%MOD
    ret %= MOD
if ans[0] == 1 and D[0] == 0:
    print(ret)
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
t = [int(x) for x in input().split()]
s=sorted(t)
deep,a,b,c = 0,1,0,1
for i in range(n):
  if s[i] == deep:
    b += 1
  elif i == n:
    c *= a ** b
  elif s[i] == deep + 1:
    c *= a ** b
    a = b
    b = 1
    deep += 1
  else:
    c = 0
    break
    
  if i == n-1:
    if s[i] == deep:
      c *= a ** b
      c = c % 998244353
    elif s[i] == deep + 1:
      c *= a ** b
      c = c % 998244353
    else:
      c = 0
      break

if s.count(0) != 1:
  print(0)
elif t[0] != 0:
  print(0)
else:
  print(c)

Submission status: Accepted

Solution code:
mod = 998244353
 
N = int(input())
D = [int(x) for x in input().split()]
 
dep = max(D)
dict = [0]*(dep+1)

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

Submission status: Accepted

Solution code:
from collections import Counter

mod = 998244353

N, *D = map(int, open(0).read().split())

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

ans = 1
for i in range(2, max(C.keys(), default=0) + 1):
    ans *= pow(C[i - 1], C[i], mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter 
import sys

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    sys.exit()
    
mod = 998244353
D.sort()
d = list(Counter(D).items()) 

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
max = 0
dd=[0]*10**5
for i in d:
    dd[i]+=1
    if(max<i):
        max=i
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)

Submission status: Accepted

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


def main():
    MOD = 998244353
    N = int(input())
    D = [int(x) for x in input().split()]
    c = collections.Counter(D)
    S_D = sorted(D)

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

    count = 1
    for i in range(1, max(D) + 1):
        count *= pow(c[i - 1], c[i])

    print(count % MOD)




    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
M = 998244353
N = int(input())
D = list(map(int, input().split()))
counter = Counter(D)
ans = 1
pre_c = 1
if D[0] != 0 or counter[0] != 1:
    print(0)
else:
    for i, (k, c) in enumerate(sorted(counter.items(), key=lambda x: x[0])):
        if k == 0:
            continue
        elif i != k:
            ans = 0
            break
        ans *= pre_c ** c
        pre_c = c
    print(ans%M)

Submission status: Accepted

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

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

#output
from collections import Counter
l = Counter(D).most_common()
l = sorted(l, key = lambda x:x[0])
M = len(l)

answer = 1

if D[0] != 0:
    answer = 0
elif l[0][1] != 1:
    answer = 0
else:
    for i in range(M-1):
        if l[i][0] + 1 != l[i+1][0]:
            answer = 0
for i in range(M-1):
    answer *= pow(l[i][1],l[i+1][1])
print(answer % 998244353)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(i) for i in input().split()]
out = 0
if d[0]:
    out = 1
d.sort()
k = [0]*100005
for i in d:
    k[i] += 1
c = 1
for i in range(d[n-1]):
    for j in range(k[i+1]):
        c *= k[i]
        c %= 998244353
if (k[0] >= 2 or out):
    print(0)
else:
    print(c)

Submission status: Accepted

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

tree_list = [0] * (max_D+1)
for idx, d in enumerate(D):
    tree_list[d] += 1
count = 1
for idx, tree in enumerate(tree_list):
    if idx == 0:
        count *= 1
    else:
        if tree == 0:
            count = 0
        else:
            count *= tree_list[idx - 1]**tree

if tree_list[0] != 1 or D[0] != 0:
    print(0)
    quit()
else:
    print(int(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()
    
a = [0] * n
for i in range(n):
    a[d[i]] += 1

ans = 1
for i in range(n):
    if i == 0:
        if a[i] != 1:
            ans *= 0
    else:
                for _ in range(a[i]):
                    ans *= a[i-1]
                    ans %= MOD
print(ans % 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)