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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = float('INF')

#A
def A():
    n = II()
    n -= 1
    print(n // 2)
    return

#B
def combination_mod(n, k, mod=mod):
    """ power_funcを用いて(nCk) mod p を求める """ 
    """ nCk = n!/((n-k)!k!)を使用 """

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod
    

def B():
    n = II()
    d = LI()
    dic = defaultdict(int)
    if d[0] != 0:
        print(0)
        return
    for di in d[1:]:
        dic[di] += 1
    ans = 1
    di = list(dic.items())
    di.sort()
    if di[0][0] != 1:
        print(0)
        return
    for i in range(len(di) - 1):
        if di[i][0] != di[i + 1][0] - 1:
            print(0)
            return
    be = 1
    for _, b in di:
        ans *= pow(be, b, mod)
        be = b
        ans %= mod
    print(ans)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

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


def main():
    mod = 998244353
    N = int(input())
    D = list(map(int, input().split()))
    if D[0] != 0 or D.count(0) != 1:
        print(0)
        return
    DD = dict()
    for d in D:
        if d in DD:
            DD[d] += 1
        else:
            DD[d] = 1
    li = sorted(DD.items(), key=lambda x:x[0])
    ans = 1
    x = 0
    pre_v = 1
#    print(li)
    for k, v in li:
        if k != x:
            print(0)
            return
        ans *= (pre_v**v)
        ans = ans % mod
#        print(pre_v, x, k, v, ans)
        pre_v = v
        x += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
u = 998244353

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

for i in range(1,N):
    d = A[i]
    if d==0:
        print(0)
        exit()
    if d in dp:
        dp[d] +=1
    else:
        dp[d] = 1

M = max(A)
ans = 1
pre = 1
for i in range(1,M+1):
    if not i in dp:
        print(0)
        exit()
    k = dp[i]
    now = pre**k
    ans *= now
    ans %= u
    pre = k
print(ans)

Submission status: Accepted

Solution code:
CONST = 998244353
n = int(input())
d = list(map(int, input().split()))
l = [0 for i in range(n)]
max_d = max(d)
for i in d:
  l[i] += 1
ans = 1
cnt = 0
prev = 1
if d[0] != 0:
  print(0)
elif l[0] != 1:
  print(0)
else:
  for i in range(max_d+1):
    cnt = l[i]
    ans *= prev**cnt%CONST
    prev = cnt
  print(ans%CONST)

Submission status: Accepted

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

mod = 998244353

def power_func(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

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

A = Counter(D)
B = sorted(A.items())

if D[0] != 0:
    print(0)
else:
    ans = 1
    for i, (k, num) in enumerate(B):
        if i == 0:
            if num != 1:
                ans = 0
                break
            pre = 0
            continue
        if k != pre + 1:
            ans = 0
            break
        if k == 1:
            pre = 1
            p = num
            continue
        ans = ans * power_func(p, num, mod) % mod
        p = num
        pre = k
    
    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)
else :
  D_dict  = collections.Counter(D)
  if D_dict[0] > 1 :
    print(0)
    exit()
  result = 1
  for i in range(1, len(D_dict)) :
    if D_dict[i] == 0 :
      print(0)
      exit()
    else :
      result *= D_dict[i-1]**D_dict[i]
      result = result % mod

  print(result)

Submission status: Accepted

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

Submission status: Accepted

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

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

mod = 998244353
ans = 1

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

d.sort()

for i in range(n-1):
    if d[i+1] - d[i] > 1:
        print(0)
        exit()

count = 1
count2 = 0
li = [1]

for i in range(1,n):
    if count == d[i]:
        count2 += 1
    else:
        li.append(count2)
        count += 1
        count2 = 1

if count2 != 1:
    li.append(count2)
else:
    if count == d[-1]:
        li.append(1)
    else:
        print(0)
        exit()

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

print(ans)

Submission status: Accepted

Solution code:
import collections

MOD=998244353
N=int(input())
D=list(map(int, input().split()))
c=collections.Counter(D)
counter=sorted(c.items(), key=lambda x:x[0])
if D[0]!=0 or counter[0][1]>1:
  print(0)
else:
  flag=True
  pre=0
  for i in range(1, len(counter)):
    if pre+1!=counter[i][0]:
      flag=False
      break
    pre+=1
  if not flag:
    print(0)
  else:
    ans=1
    for i in range(2, len(counter)):
      for j in range(counter[i][1]):
        ans=(ans*counter[i-1][1])%MOD
      #ans=(ans*(counter[i-1][1]**counter[i][1])%MOD)%MOD
    print(ans)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time

setrecursionlimit(10**6)
input=stdin.readline

n=int(input())
d=[int(i) for i in input().split()]
m=max(d)
if d[0]!=0:
    print(0)
    exit()
dst=[0]*(m+1)
ans=1
for i in d: dst[i]+=1
#print(*dst)
if dst[0]>1:
    print(0)
    exit()
for i in range(2,m+1):
    if dst[i]==0:
        print(0)
        exit()
    ans*=dst[i-1]**dst[i]
print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
d_array = list(map(int, input().split()))
if d_array[0] != 0:
    print(0)
else:
    count = [0 for _ in range(n)]
    count[0] = 1
    for d in d_array[1:]:
        count[d] += 1
    i = 1
    node = 1
    ans = 1
    while node < n and i < n:
        if count[i] == 0:
            ans = 0
            break
        ans *= count[i - 1] ** count[i]
        ans %= 998244353
        node += count[i]
        i += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
t=tuple(map(int,input().split()))
while True:
  if t[0]!=0:
    print(0)
    break
  m=max(t)
  a=[0]*(m+1)
  for i in range(n):
    a[t[i]]+=1
  a=tuple(a)
  if a[0]!=1:
    print(0)
    break
  s=1
  for i in range(m):
    s=(s*(a[i]**a[i+1]))%998244353
  print(s)
  break

Submission status: Accepted

Solution code:
import collections
import sys

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

max_nums = max(nums)
cnt_list = collections.Counter(nums)
#print(cnt_list)

ans = 1
if cnt_list[0] == 1 and nums[0] == 0:
	for i in range(1, max_nums + 1):
		if cnt_list[i] == 0:
			print(0)
			sys.exit()
		else:
			ans *= (cnt_list[i - 1] ** cnt_list[i]) % 998244353
			#print(ans)
	print(ans % 998244353)

else:
	print(0)

Submission status: Accepted

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque

from collections import Counter
P = 998244353
N = int(readline())
D = list(map(int, readline().split()))

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

def mod_pow(a, b):
    ret = 1
    for i in range(b):
        ret = ret * a % P
    return ret

if D[0] != 0 or c[0][1] != 1:
    print(0)
else:
    ans = 1
    for i in range(1, len(c)):
        if c[i - 1][0] != c[i][0] - 1:
            print(0)
            exit(0)
        ans = ans * mod_pow(c[i-1][1], c[i][1]) % P
    print(ans)

Submission status: Accepted

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


if D[0] != 0 or 0 in D[1:]:
    ans = 0
else:
    num = [0 for i in range(max(D)+1)]
    ans = 1
    cnt = 1
    for i in range(n):
        num[D[i]] += 1
    for i in range(len(num)):
        ans = ans * (cnt ** num[i]) % 998244353
        cnt = num[i]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = [int(d) for d in input().split()]
D0 = D[0]
D1 = sorted(D[1:])

def calc(D1):
    r = 1
    m = {0:1}
    for d in D1:
        if d-1 in m:
            r = r * m[d-1] % 998244353
            if d in m:
                m[d] = m[d] + 1
            else:
                m[d] = 1
        else:
            return(0)
    return(r)

if D0 != 0:
    print(0)
else:
    print(calc(D1) % 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()))
dmax = max(D)
M = 998244353

if D[0]!=0:
	ans = 0
else:
	D = Counter(D)

	if D[0]!=1:
		ans = 0
	else:
		ans = 1
		for i in range(1,dmax+1):
			if D[i]==0:
				ans = 0
				break
			ans *= D[i-1]**D[i]
			ans = ans%M

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


MOD = 998244353


def power(a, n, p=MOD):
    res = 1
    for _ in range(n):
        res *= a
        res %= p
    return res


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

d = Counter(sorted(d))
if d[0] > 1:
    print(0)
    exit(0)

d = sorted(d.items())
prev_index = -1
prev_count = 1

ans = 1
for k, v in d:
    if k != prev_index+1:
        print(0)
        exit(0)
    ans *= power(prev_count, v)
    ans %= MOD
    prev_index = k
    prev_count = v
print(ans)

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

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

keys = sorted(dic.keys())
prev_num = 0
prev_count = 1
ans = 1
for num in keys:
    if num == 0:
        continue

    if num - prev_num != 1:
        print(0)
        exit()

    count = dic[num]
    ans *= prev_count ** count
    ans %= mod
    prev_num = num
    prev_count = count

print(ans)

Submission status: Accepted

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

if D[0] != 0:
  print(0)
else:
  flag = True
  D.sort()
  dic = {}
  prev = -1
  for i in D:
    if i not in dic:
      dic[i] = 1
      if(i != prev + 1):
        flag = False
      else:
        prev = i
    else:
      dic[i] += 1
  prev = -1
  cnt = 1
  if dic[0] != 1:
    flag = False
  if flag:
    for k in dic:
      if k > 0:
        t = 1
        for j in range(dic[k]):
          t *= dic[k - 1]
        cnt *= t
  if flag:
    print(cnt % 998244353)
  else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input().strip())
D = list(map(int, input().strip().split()))
tmpD = D[1:]
tmpD = sorted(tmpD)




# D[0]!=0ならば0
if D[0] != 0 or tmpD[0] == 0:
    print(0)
else:
    ans = 1
    max_depth = max(tmpD)
    count = [0] * (max_depth+1)
    for num in tmpD:
        count[num]+=1
    for i in range(1, max_depth):
        ans *= (count[i]**count[i+1])
        ans %= 998244353
    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()

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

if n == 2:
    if d[1] == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()


a = [0]*n

while d:
    s = d.pop()
    a[s] += 1

if a[0] >= 2:
    print(0)
    exit()

ans = 1

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

print(ans % mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#NIKEI B
import sys
import math
import collections
#sys.setrecursionlimit(100000)


n=int(input())

tmp = input().split()
d = list(map(lambda a: int(a), tmp))

max=0
numlist={}
for i in range(0,n):
	if(d[i]>max):
		max=d[i]
	if(d[i] in numlist):
		numlist[d[i]]+=1
	else:
		numlist[d[i]]=1


if(d[0]!=0):
	print(0)
	sys.exit()
for i in range(max):
	if not(i in numlist):
		print(0)
		sys.exit()
if(numlist[0]!=1):
	print(0)
	sys.exit()


ans=1
for i in range(1,max):
	#print(numlist[i])
	ans=ans*numlist[i]**numlist[i+1]

print(ans % 998244353)

Submission status: Accepted

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

if D[0] != 0:
    print(0)
    exit()
D.sort()
d = {}
for i in range(D[-1] + 1):
    d[i] = 0

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

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

for i in range(1, D[-1] + 1):
    if d[i] == 0:
        print(0)
        exit()
ans = 1
for i in range(2, D[-1] + 1):
    ans *= (d[i-1]**d[i]) % 998244353
    ans = ans % 998244353
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

ans = 1
idx = 1
C = sorted(Counter(D[1:]).items())
for k, v in C:
    if k != idx:
        print(0)
        exit()
    if k == 1:
        _v = v
    else:
        ans = ans * _v ** v % 998244353
        _v = v
    idx += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#第二回全国統一プログラミング王決定戦予選 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
d = LI()
if d[0] != 0:
    print(0)
    quit()
d.sort()
d = list(Counter(d).items())
n = len(d)
if d[0][1] > 1:
    print(0)
    quit()
ans = 1
for i in range(1,n):
    j,k = d[i]
    l,m = d[i-1]
    if j != l+1:
        print(0)
        quit()
    ans *= m**k
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

mod = 998244353
c = Counter(d)

dp = [0]*n
if d[0] == 0 and c[0] == 1:
    dp[0] = 1
else:
    dp[0] = 0

for i in range(n):
    if i == 0:
        continue
    tmp = pow(c[i-1], c[i], mod)
    dp[i] = dp[i-1]*tmp % mod

ans = dp[-1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.buffer.readline()[:-1].decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 998244353

n=int(input())
D=list(map(int,input().split()))
ans=1
data=[0]*(10**5)
M=0
for i in range(n):
    data[D[i]]+=1
    M=max(M,D[i])

for i in range(1,n-1):
    ans*=data[i-1]**data[i]
    ans=ans%mod
    # print(data[i-1],data[i])

if D[0]!=0:
    ans=0
if data[0]>=2:
    ans=0
for i in range(M):
    if data[i] ==0:
        ans=0

print(ans%mod)
# print(data[:20])

Submission status: Accepted

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

n = int(input())
d = [int(item) for item in input().split()]
if d[0] != 0:
    print(0)
    exit()
max_val = max(d)
cnt = [0] * (max_val + 1)
for item in d:
    cnt[item] += 1
if 0 in cnt:
    print(0)
    exit()
if cnt[0] != 1:
    print(0)
    exit()

ans = 1
for a, b in zip(cnt, cnt[1:]):
    ans *= pow(a, b, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections as co
n = int(input())
d = list(map(int,input().split()))
mod = 998244353
ans = 1
if d[0] != 0:
    print(0)
    sys.exit()

else:

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

print(ans%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res



def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = list(set(a))
    d = Counter(a)
    if a[0] != 0:
        print(0)
    elif a[0] == 0 and d[0] > 1:
        print(0)
    else:
        ans = 1
        for i in range(1, len(s)):
            if d[s[i] - 1] == 0 and s[i] > 0:
                print(0)
                exit()
            ans = (ans * modpow(d[s[i - 1]], d[s[i]], 998244353)) % 998244353
        print(ans)
            

    
    

        
        
        
            

    
   


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

def main():
    N=int(input())
    if N==0:
        return 0
    DL=[int(x) for x in input().split()]
    if DL[0]!=0:
        return 0
    
    
    dic=collections.Counter(DL)
    if dic[0]!=1:
        return 0
    keys=dic.keys()
    result=1
    for i in range(1,max(keys)+1):
        if dic[i]==0 and dic[i-1]==0:
            return 0
        result*=dic[i-1]**dic[i]

    return result%998244353


print(main())

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
flag = True
if d[0] != 0:
    flag = False
count = {}
for i in range(len(d) - 1):
    count.setdefault(d[i + 1], 0)
    count[d[i + 1]] += 1
count2 = []
for i, j in count.items():
    count2.append([i, j])
count2.sort()

ans = 1
if count2[0][0] == 1:
    for i in range(len(count2) - 1):
        if count2[i + 1][0] - count2[i][0] == 1:
            temp = count2[i][1] ** count2[i + 1][1]
            ans *= temp
            ans %= mod
        else:
            flag = False
            break
else:
    flag = False
if flag == True:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
n = int(input())
d = list(map(int, input().split()))
if d[0] != 0:
    print(0)
    sys.exit()
d.sort()
d.append(-1)
if d[1] == 0:
    print(0)
    sys.exit()
i = 1
distance = 1
count = 0
while d[i] == distance:
    count += 1
    i += 1
branch = count
ans = 1
while True:
    count = 0
    distance += 1
    while d[i] == distance:
        count += 1
        i += 1
    ans *= (branch**count)%998244353
    branch = count
    if i >= n:
        break
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

counts = Counter(D)
Dmax = max(D)

flg = True
if D[0] != 0:
    flg = False
if counts[0] != 1:
    flg = False

if flg:
    ans = 1
    for i in range(1,Dmax+1):
        ans *= counts[i-1]**counts[i]
        ans %= 998244353
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

def main():
    d1 = D.pop(0)
    if d1 != 0:
        print(0)
        exit()

    c = Counter(D)
    item_list = list(c.items())
    item_list.sort()
    if item_list[0][0] != 1:
        print(0)
        exit()
    count = 1
    ans = 1
    item_list[0]
    for i in range(1, len(item_list)):
        if item_list[i][0] != count + 1:
            print(0)
            exit()
        count += 1
        ans *= (item_list[i-1][1]**item_list[i][1]) % MOD
        ans %= MOD
    
    print(ans)

if __name__ == "__main__":
    main()

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

cnt = collections.Counter(d)
total = 1
p = 1
if cnt[0] > 1:
    print(0)
    exit()
for i in range(1, n):
    if p == 0 and cnt[i] > 0:
        print(0)
        exit()
    total *= p**cnt[i]
    total %= mod
    p = cnt[i]
print(total % mod)

Submission status: Accepted

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

ans = 1
cnt = [0] * (n)

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

if d[0] != 0 or cnt[0] > 1:
  ans = 0
else:
  for i in range(2,n):
    ans *= cnt[i-1] ** cnt[i]
    ans %= 998244353

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

if D[0] != 0 or a[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, N):
        ans = (ans * pow(a[i - 1], a[i], MOD)) % MOD
        # print(ans)
        # ans = pow(ans, max(a[i] * D[i - 1], 1), MOD)
print(ans)

Submission status: Accepted

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

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


d.sort()
c = collections.Counter(d)

if c[0] != 1:
    print("0")
    sys.exit()
    
ans = 1
for i in range(len(c)-1):
    x = c[i] ** c[i+1]
    ans *= x
    ans = ans % 998244353


print(ans)

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
a = words(int)

mv = max(a)

xs = [0] * (mv+1)
for y in a:
    xs[y] += 1

#print(xs)

if xs[0] > 1:
    print(0)
elif a[0] != 0:
    print(0)
else:
    ans = 1
    for i in range(len(xs)-1):
        ans *= xs[i] ** xs[i+1]
        ans %= 998244353

    print(ans)

Submission status: Accepted

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

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

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

D.sort()
if D[1] == 0:
    print(0)
    exit()

gr = itertools.groupby(D[1:])
rank = 1
pre = 1
ans = 1
for key, group in gr:
    if rank != key:
        print(0)
        exit()
    cand = len(list(group))
    ans *= pre ** cand
    ans %= mod
    pre = cand
    rank += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
mod = 998244353
from collections import defaultdict
C = dict()
for i in range(max(D)+1):
    C[i] = 0
if D[0] > 0 or D.count(0) != 1:
    print(0)
    exit()
for e in D:
    C[e] += 1
ans = 1
for key,item in C.items():
    if key == 0:
        continue
    if item == 0:
        print(0)
        exit()
    ans *= int(C[key-1]**item)
    ans = ans % mod
print(ans)

Submission status: Accepted

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

MOD = 998244353

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


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

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

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

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

    if A[0] > 1:
        print(0)
        return
    
    x = 1

    for i in range(1, len(A)):
        x *= modPow(A[i-1], A[i], MOD)
        x %= MOD

    print(x)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
mod = 998244353

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

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

D = sorted(D)
c = Counter()
c[-1] += 1
ans = 1

for d in D:
    ans *= c[d-1]
    ans %= mod
    c[d] += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
mod=998244353
from collections import Counter
dd=Counter(d)
if not(d[0]==0 and sorted(d)[1]!=0):print(0);exit()
d.sort()
a=1
for i in range(1,d[-1]+1):
  if dd[i]==0:a*=0
  else:a*=dd[i-1]**dd[i]
  a%=mod
print(a)

Submission status: Accepted

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

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

d = Counter(D)

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

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

Submission status: Accepted

Solution code:
import sys

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

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

d.sort()
if n >=2:
    if d[1] == 0:
        print(0)
        sys.exit()

for i in range(n-1):
    if d[i]>d[i+1] or d[i]+1<d[i]:
        print(0)
        sys.exit()

m = max(d)

cnt = {i:0 for i in range(1,m+1)}

for i in range(1,n):
    cnt[d[i]] += 1
mod = 998244353

ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
m=998244353
n=int(input())
s=list(map(int,input().split()))
from collections import Counter as co
if s[0]!=0:
  print(0)
else:
  s=s[1:]
  if 0 in s:
    print(0)
  else:
    ans=1
    d=co(s)
    l=max(s)
    x=d.get(1,0)
    for i in range(2,l+1):
      y=d.get(i,0)
      ans=(ans*(x**y))%m
      x=y
    print(ans%m)

Submission status: Accepted

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

c=collections.Counter(d)
ans=1
ans=c[0]

if ans==1 and d[0]==0:
    for i in range(1,len(c)):
        ans*=(c[i-1]**c[i])%998244353
    print(ans%998244353)
else:
    print(0)

Submission status: Accepted

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

import sys
mod = 998244353
n = int(input())
dl = list(map(int,input().split()))

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

before = 0
for i in dl:
    if i - before > 1:
        print(0)
        sys.exit()
    before = i
    
if dl.count(0) > 1:
    print(0)
    sys.exit()    
    

ans = 1
before_e = 1
now_e = 0
now = 0

for d in dl:
    if now != d:
        if now_e == 0:
            print(0)
            sys.exit()
        before_e = now_e
        now_e = 0
        now += 1
    now_e += 1
    ans *= before_e
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

MOD = 998244353

n = ri()
ls = ril()

counter = collections.Counter(ls)
if ls[0] > 0 or counter[0] > 1:
    print(0)
    exit()

res = 1
for i in range(2, max(counter.keys()) + 1):
    if counter[i - 1] == 0:
        print(0)
        exit()
    res *= counter[i - 1]**counter[i]
    res %= MOD
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
if d[0] != 0:
  print(0)
  exit()
c = [0 for _ in range(n)]
for i in range(1,n):
  if d[i] == 0:
    print(0)
    exit()
  else:
    c[d[i]] += 1
res = 1
for i in range(n-1,1,-1):
  if c[i] != 0:
    res = (res*(c[i-1]**c[i]))%(998244353)
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 998244353

N = int(input())
D = list(map(int, input().split()))
if D[0] != 0 or D.count(0) != 1:
    print(0)
    exit()
c = Counter(D)
if len(set(D)) != max(D) + 1:
    print(0)
    exit()
answer = 1
prev = 1
for k, v in c.items():
    answer *= prev ** v
    answer %= MOD
    prev = v
print(answer)

Submission status: Accepted

Solution code:
import collections

mod = 998244353
n = int(input())


def pow(n, p):
    if p == 1:
        return n
    if p % 2 == 0:
        return (pow(n, p // 2) ** 2) % mod
    else:
        return ((pow(n, p // 2) ** 2) * n) % mod


def main():

    d = list(map(int, input().split()))
    if d[0] != 0:
        return 0

    md = max(d)
    cd = collections.Counter(d)
    res = cd[0]
    if res != 1:
        return 0
    for i in range(1, md + 1):
        if cd[i] == 0:
            return 0
        res *= pow(cd[i - 1], cd[i])
        res %= mod
    return res


print(main() % mod)

Submission status: Accepted

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