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:
import collections
N = int(input())

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

counted = collections.Counter(D)

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

#calc
result = 1
x = counted[1]
for i in range(2,N+1):
    y = counted[i]
    result = result * pow(x,y) %998244353
    x = y
print(result)

Submission status: Accepted

Solution code:
import sys
import collections

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

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

if c==[(0,1)]:
	print(1)
	sys.exit()

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

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

print(ans%mod)

Submission status: Accepted

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

L = [0] * N

for d in D:
    L[d] += 1
if D[0] != 0:
    print(0)
    sys.exit()
total = 1
prev_l = 1
for i, l in enumerate(L):
    if i == 0:
        prev_l = l
        if l != 1:
            total = 0
            break
        continue
    total *= (prev_l**l)
    total %= MOD
    prev_l = l

print(total%MOD)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
ans=1
a=1
b=1
if n==1 or d[0]!=0:
    ans=0
d=sorted(d)
for j in range(0,n-1):
        if d[j+1]-d[j]>1:
            ans=0
            break
        
if d[0]!=0 or d[1]==0:
    ans=0
else:
    for i in range(1,n-1):
        if d[i]==d[i+1]:
            a+=1
        else:
            ans=ans*(b**a)
            b=a
            a=1
ans=ans*(b**a)
ans=ans%998244353
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

N = int(input())
D_list = list(map(int, input().split()))
if D_list[0] != 0:
    print(0)
    sys.exit()
P = 998244353
n = 1
c = Counter(D_list)
if c[0] != 1:
    print(0)
else:
    pre = 1
    for i in range(1, max(D_list) + 1):
        if c[i] == 0:
            print(0)
            sys.exit()
        n = (n * ((pre ** c[i]) % P)) % P
        pre = c[i]
    print(n)

Submission status: Accepted

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

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

waru = 998244353

dic = {}
dic2 = {}

for i in range(1, N+1):
    dic[i] = D[i-1]

for number, distance in dic.items():
    if distance in dic2:
        dic2[distance] = dic2[distance] + 1
    else:
        dic2[distance] = 1

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

l = []

for i in range(1, len(dic2.items()) - 1):
    if i in dic2 and (i+1) in dic2:
        l.append(dic2[i] ** dic2[i+1])
    else:
        print(0)
        exit(0)

r = 1
for x in l:
    r *= x

d, m = divmod(r, waru)
print(m)

Submission status: Accepted

Solution code:
import os
N=int(input())
a=list(map(int, input().split()))
if not (a[0]==0):
  print(0)
else:
  m=max(a)
  b=[0]*m
  flag=True
  for i in a[1:]:
    if i==0:
      print(0)
      flag=False
    b[i-1]+=1
  if flag:
    res=1
    #print(b)
    for i in range(1,len(b)):
      res*=b[i-1]**b[i]

    print((res)%998244353)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int,raw_input().split())

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

a.sort()

if a[1] != 1:
  print 0
  exit(0)
  
ans = 1
old = 1
now = 1
c = 0

for q in range(1,len(a)):
  ans %= 998244353

  if now != a[q]:
    if now+1 != a[q]:
      print 0
      exit(0)
    else:
      ans = ans * pow(old,c,998244353)
      old = c
      c = 1
      now = a[q]
  else:
    c += 1
ans = ans * pow(old,c,998244353)

ans %= 998244353
print ans

Submission status: Accepted

Solution code:
#b
n=int(input())
d=[int(i) for i in input().split()]

import collections
c = collections.Counter(d)

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

Submission status: Accepted

Solution code:
import sys
MM = 998244353
n, = map(int, input().split())
xs = list(map(int, input().split()))
mm = max(xs)
cc = [0] * n
if xs[0] != 0:
    print(0)
    sys.exit()
for x in xs:
    cc[x] += 1
for i in range(mm+1):
    if cc[i] == 0:
        print(0)
        sys.exit()
if cc[0] != 1:
    print(0)
    sys.exit()
r = 1
for i in range(mm):
    r = (r * pow(cc[i], cc[i+1])) % MM
print(r)

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
import collections
dat = list(map(int, input().split()))
c = collections.Counter(dat)
ma = max(c)
#print(c)
res = 1
#print(c)
can = True

for i in range(1,ma ):
    #print("{0} ^ {1}".format(i, i+1))
    #print("={0} ^ {1}".format(c[i], c[i+1]))
    #res *= c[i] ** (c[i+1])
    if c[i] == 0:
        can = False
        break
    for ii in range(c[i+1]):
        res *= c[i]
        res %= mod
        #print("=={0}".format(res))


if dat[0] != 0:
    print(0)
elif c[0] != 1:
    print(0)
elif can is False:
    print(0)
else:
    print(res)

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
DD = inpl()
cnts = defaultdict(int)
for d in DD:
    cnts[d] += 1

m = max(DD)

if DD[0] != 0 or cnts[0] != 1:
    print(0)
else:
    ans = 1
    for i in range(1,m+1):
        if cnts[i] == 0:
            print(0)
            sys.exit()
        ans *= pow(cnts[i-1],cnts[i],mod)
        ans %= mod

    print(ans%mod)

Submission status: Accepted

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

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

count = 1
dmax = max(d)
num_array = [0] * (dmax+1)

for i in range(len(d)):
    num_array[d[i]] += 1

if num_array[0] != 1:
    print("0")
    exit()
for i in range(1, dmax+1):
    count *= num_array[i-1] ** num_array[i]
    count %= 998244353
print(count)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


def main():
    N = int(input())
    D = list(map(int, input().split()))
    count = Counter(D)
    result = 1
    if D[0] != 0 or count[0] != 1:
        print(0)
        return
    for i in range(max(D)):
        result *= count[i] ** count[i + 1]
    print(result % 998244353)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

cnt = collections.Counter(D)
if cnt[0] != 1:
    print(0)
    exit()
    
ans = 1
limit = max(cnt.keys()) + 1
for i in range(0, limit):
    if i == limit - 1:
        break
    n = cnt[i]
    r = cnt[i + 1]
    if n == 0 or r == 0:
        ans = 0
        break
    ans *= n ** r

print(ans % 998244353)

Submission status: Accepted

Solution code:
import numpy as np
import collections

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

D_seq_max = max(D_seq)

judge_list = np.arange(D_seq_max+1)
judge_set = set(judge_list)
D_seq_set = set(D_seq)

c = collections.Counter(D_seq)

N_list = []
if((judge_set == D_seq_set)and(D_seq[0]==0)):
    if(c[0]>1):
        print(0)
    else:
        counts = 1
        for i in range(D_seq_max):
            counts *= pow(c[i], c[i+1])
        if(counts < 998244353):    
            print(counts)
        else:
            print(int(counts%998244353))
else:
    print(0)

Submission status: Accepted

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
k=max(ls)
ls2=[0 for i in range(k+1)]
for e in ls:
  ls2[e]+=1
if ls2[0]!=1 or ls[0]!=0:
  print(0)
else:
  ans=1
  for i in range(1,k):
    for j in range(ls2[i+1]):
      ans=(ans*ls2[i])%998244353
  print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
 
N = int(input())
D = list(map(int,input().split()))
 
C = [0]*N
 
for i in range(N):
    C[D[i]]+=1
 
if D[0]!=0:
    print(0)  
elif C[0]==1:
    counter=1
    ans = 1
    for i in range(1,N):
        if C[i]==0 and counter<N:
            ans = 0
            break
        elif C[i]==0:
            break
        else:
            ans *= pow(C[i-1] ,C[i], mod)
            ans %= mod
            counter += C[i]
    print(ans)
else:
    print(0)

Submission status: Accepted

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

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

D.sort()
ans = 1
count = {}
for i in range(N):
  if i > 0:
    if D[i]-1 in count:
      ans *= count[D[i]-1]
      ans %= MOD
    else:
      print(0)
      exit()
  if D[i] in count:
    count[D[i]] += 1
  else:
    count[D[i]] = 1
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353

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

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

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

if p[0]!=1:
    print(0)
    exit()
ans = 1
j = 1
for i in range(1,n):
    if p[i]==0:
        break

    ans = (ans*(p[i-1]**p[i]))%mod
    j +=p[i]
if j==n:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

import collections
dic = collections.Counter(D)

maxkey = max(dic.keys())

ans=dic[0]
if ans == 1 and D[0] == 0:
    for i in range(1,maxkey): 
        ans=ans*(dic[i]**dic[i+1])%MOD
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
mod = 998244353
kaizyo = [1, 1]
for i in range(2, 100005):
    kaizyo.append(kaizyo[-1]*i % mod)

# print(kaizyo[:10])


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

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

prime_D = set(D)
prime_D = list(prime_D)
counter = {}

for i in range(len(prime_D)):
    counter[prime_D[i]] = 0

for i in range(len(D)):
    counter[D[i]] += 1  # 数を数えた

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

if counter[0][1] > 1:
    print(0)  # 1との距離が0のものがあったらアウト
    exit()

# 距離が2離れているものは定義できない
now = counter[0][0]
for i in range(1, len(counter)):
    if counter[i][0] != (now+1):
        print(0)
        exit()
    now = counter[i][0]

# これですべての例外は弾けた
ans = 1
for i in range(1, len(counter)):
    ans *= counter[i-1][1]**counter[i][1]


print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
import collections as col
E = col.Counter(D)
def tree(L):
    t = 1
    if L[0] != 1:
        return 0
    else:
        for i in range(1,len(L)):
            t = t * (L[i-1]**L[i])
            t = t % 998244353
        return t
def number(D,E):
    if D[0] == 0:
        return tree(E)
    else:
        return 0
print(number(D,E))

Submission status: Accepted

Solution code:
LARGE = 998244353


def solve(n, d_list):
    cnt = [0] * (max(d_list) + 1)
    for i in range(n):
        cnt[d_list[i]] += 1
    if cnt[0] != 1 or d_list[0] != 0:
        return 0
    res = 1
    for i in range(max(d_list)):
        res *= pow(cnt[i], cnt[i + 1], LARGE)
        res %= LARGE
    return res


def main():
    n = int(input())
    d_list = list(map(int, input().split()))
    res = solve(n, d_list)
    print(res)


def test():
    assert solve(4, [0, 1, 1, 2]) == 2
    assert solve(4, [1, 1, 1, 1]) == 0
    assert solve(7, [0, 3, 2, 1, 2, 2, 1]) == 24


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

Submission status: Accepted

Solution code:
N=int(input())
ld=list(map(int,input().split()))
def modpow(a,n,p):#a^n mod p
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res
if ld[0]!=0:
    print(0)

else:
    dd={}
    for i in range(N):
        if ld[i] in dd:
            dd[ld[i]]+=1
        else:
            dd[ld[i]]=1

    if dd[0]!=1:
        print(0)
    else:
        DV=998244353
        ans=1
        for i in range(0,len(dd)-1):
            #mul=dd[i]**dd[i+1]%DV
            if i in dd and i+1 in dd:
                mul=modpow(dd[i],dd[i+1],DV)
                #ans*=dd[i]**dd[i+1]
                ans*=mul
                ans%=DV
            else:
                print(0)
                break
        else:
            print(ans)

Submission status: Accepted

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

import collections
c = collections.Counter(d)
if d[0] == 0:
    if c[0] != 1:
        print(0)
    else:
        result = 1
        for i in range(1, len(c)):
            result *= c[i-1]**c[i]
            result = result%998244353
        print(result)
else:
    print(0)

Submission status: Accepted

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

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

count = 1
dmax = max(d)
num_array = [0] * (dmax+1)

for i in range(len(d)):
    num_array[d[i]] += 1

if num_array[0] != 1:
    print("0")
    exit()
if 0 in num_array:
    print("0")
    exit()
for i in range(1, dmax+1):
    count *= num_array[i-1] ** num_array[i]
    count %= 998244353
print(count)

Submission status: Accepted

Solution code:
import collections
n = int(input())
d = [int(i) for i in input().split()]
ans = 0
if d[0] == 0:
    s = collections.Counter(d)
    ss = sorted(s.items())
    if ss[0][1] == 1:
        ans = 1
        for i in range(1,len(ss)):
            if ss[i][0] != ss[i-1][0] + 1:
                ans = 0
                break
            ans *= ss[i-1][1]**ss[i][1]
print(ans%998244353)

Submission status: Accepted

Solution code:
import math

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

ans = -1

d_count = [0] * (max(d)+1)
for i in range(n):
  d_count[d[i]] += 1

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

ans = 1
for i in range(1,len(d_count)-1):
  for j in range(d_count[i+1]):
    ans = ans * d_count[i]
    ans = ans % 998244353

ans = ans % 998244353

print(int(ans))

Submission status: Accepted

Solution code:
import collections
import operator

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

D_dict = collections.Counter(D)
D_dict_sorted = sorted(D_dict.items(), key=operator.itemgetter(0))

# l = []
# for i in range(int(max(D))):
#     if D_dict_sorted[i][0] + 1 == D_dict_sorted[i+1][0]
#     l.append()

if (D[0] == 0) and (D_dict_sorted[0][1] == 1) :
    ans = 1
    for i in range(len(D_dict_sorted)-1):
        if D_dict_sorted[i][0] + 1 == D_dict_sorted[i+1][0]:
            ans *= D_dict_sorted[i][1] ** D_dict_sorted[i+1][1]
            if ans >= 998244353:
                ans = ans % 998244353
        else:
            ans = 0
else:
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
s = list(map(int, input().split()))
item = 0
sum = 0
node = 0
count = 0
before = 0


c = collections.Counter(s)

for i in range(N):
    count = c[i]
    node += count

    if i == 0:
        if count != 1:
            break
        else:
            before = 1
            sum = 1
    else:
        if count == 0:
            break
        else:
            sum = sum * (c[i-1] ** count)
            before = count

if node != len(s) or s[0] != 0:
    print("0")
else:
    print(sum%998244353)

Submission status: Accepted

Solution code:
import collections

n=int(input())
d=list(map(int,input().split()))
if d[0]!=0:
  print(0)
elif 0 in d[1:]:
  print(0)
else:
  dic=collections.Counter(d[1:])
  sorted(dic)
  p=1
  for i in range(1,len(dic)):
    p*=dic[i]**dic[i+1]
  print(p%998244353)

Submission status: Accepted

Solution code:
import sys
import bisect

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

for i, d in enumerate(D):
    if d != 0 and i == 0:
        print(0)
        sys.exit()

    elif d == 0 and i != 0:
        print(0)
        sys.exit()

D.sort()


ans = 1
cnt = []
for d in range(N):

    cnt.append(bisect.bisect(D, d))

for d in D:
    if d == 0 or d == 1:
        continue

    ans = ans * (cnt[d - 1] - cnt[d - 2]) % 998244353


print(ans)

Submission status: Accepted

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = [int(e) for e in lines[0].split(" ")][0]
    d = [int(e) for e in lines[1].split(" ")]

    return (n, d)


def solve(n, d):

    if d[0] != 0:
        return 0 
     
    d.sort()

    z = [] 
    tmp = d[0]
    count = 0
    for i in range(n):
        if tmp != d[i]:
            z.append((tmp, count))
            tmp = d[i]
            count = 1
        else:
            count = count + 1
    z.append((tmp, count))

    if z[0][0] != 0 or z[0][1] > 1:
        return 0

    result = 1
    m = len(z)
    for i in range(1, m):
        if z[i-1][0] + 1 != z[i][0]:
            result = 0
            break
        else:
            result = result * z[i-1][1] ** z[i][1]
    
    res = result % 998244353

    return res


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


N = int(input())

dList = [int(i) for i in input().split()]
ispossible = True

if dList[0] != 0:
    ispossible = False
dList.pop(0)

amari = 998244353
dList.sort()

if dList[0] <= 0:
    ispossible = False


sameDistanceCount = 1
prevdistance = 0
branch = 1
count = 1

for i in range(N-1):
    nowdistance = dList[i]
    if nowdistance - prevdistance >= 2:
        ispossible = False
        break
    elif nowdistance == prevdistance + 1:
        for j in range(sameDistanceCount):
            count *= branch
            count %= amari
        branch = sameDistanceCount
        prevdistance = nowdistance
        sameDistanceCount = 1
    else:
        sameDistanceCount += 1


for i in range(sameDistanceCount):
    count *= branch
    count %= amari

if ispossible:
    print(count)
else:
    print(0)

Submission status: Accepted

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

boxes = [[] for i in range(N)]
impossible = False
for idx,num in enumerate(ls):
    if num>=N:
        impossible=True
        break
    boxes[num].append(idx)

check_start=-1
ans = 1

if impossible:
    ans = 0
elif len(boxes[0])==0:
    ans = 0
elif boxes[0][0]!=0:
    ans = 0
elif len(boxes[0])>=2:
    ans = 0
else:
    for i in range(N-1):
        a = len(boxes[i])
        b = len(boxes[i+1])
        if a == 0:
            check_start = i
            rest_ls = boxes[i:]
            if rest_ls.count([])!=len(rest_ls):
                ans = 0
            break
        ans*=a**b
baisu = ans//998244353
print(ans-(998244353*baisu))

Submission status: Accepted

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

num = [0] * 100000

maxd = 0
for d in D:
    num[d] += 1
    maxd = max(d, maxd)

if D[0] != 0 or num[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, maxd):
        for _ in range(num[i+1]):
            ans *= num[i]%998244353
        ans %= 998244353
        if ans == 0:
            break
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

# 累乗 x^n
def pow(x,n):
    global p
    res=1
    prod=x
    while n>0:
        if n%2==1:
            res=(res*prod)%p
        prod=(prod*prod)%p
        n//=2
    return res

p=998244353

N=int(input())
D=list(map(int,input().split())) # 頂点は0-initial

f=True
if D[0]!=0:
    f=False
else:
    C=Counter(D)
    if C[0]>1:
        f=False
    else:
        dmax=max(C)    
        for d in range(1,dmax):
            if d not in C:
                f=False
    if f:
        v=[C[i] for i in range(dmax+1)]
        ans=1
        for d in range(1,dmax):
            ans=(ans*pow(v[d],v[d+1]))%p
if f:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    mod = 998244353

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

    if d[0] > 0:
        print('0')
        exit()

    if len(d) == 1:
        print('1')
        exit()

    d.sort()
    d.pop(0)
    if d[0] == 0:
        print('0')
        exit()

    tmp = 1
    ans = 1
    max_num = max(d)
    dic = dict()
    for i in range(n-1):
        if d[i] in dic:
            dic[d[i]] += 1
        else:
            dic[d[i]] = 1

    for i in range(1, max_num+1):
        if i in dic:
            count = dic[i]
        else:
            print('0')
            exit()
        if count == 0:
            print('0')
            exit()
        ans *= tmp ** count
        ans %= mod
        tmp = count

    print(ans)

Submission status: Accepted

Solution code:
m = 998244353
def myPow(a,b):
    a %= m
    if b == 1:
        return a%m
    elif b == 0:
        return 1
    if b%2 == 0:
        return myPow(a**2,b//2)%m
    else:
        return (a%m)*myPow(a**2,(b-1)//2)%m

n = int(input())
ngo = [0]*n
d = list(map(int,input().split()))
for i in range(n):
    ngo[d[i]]+=1
if ngo[0] != 1:
    print(0)
    exit(0)
if d[0] != 0:
    print(0)
    exit(0)
ans = 1
for i in range(n-1):
    ans = (ans*myPow(ngo[i],ngo[i+1])%m)%m
print(ans%m)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
N=int(input())
D_list=[int(thing) for thing in input().split(" ")]
maxx=max(D_list)
if D_list[0] !=0:
    print(0)
    exit()
C=collections.Counter(D_list)
if C[0] != 1:
    print(0)
    exit()

ret=1
for i in range(0,maxx):
    if maxx-i not in C:
        print(0)
        exit()
    if maxx-i==0:
        pass
    else:
        ret=ret*C[maxx-i-1]**C[maxx-i]

print(ret%998244353)

Submission status: Accepted

Solution code:

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

if D[0] != 0:
    flg = False
    
D.sort()
T = [0 for _ in range(N + 1)]

for i in range(N):
    T[D[i]] += 1

i = 0
ans = 1
if T[i] != 1:
    flg = False

pre = T[i]
i += 1
while T[i] != 0:
    ans *= pow(pre,T[i])
    ans %= mod
    pre = T[i]
    i += 1

while i < N:
    if T[i] > 0:
        flg = False
    i += 1

ans %= mod
if flg:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

if D[0] != 0:
    print(0)
else:
    count = defaultdict(int)
    for d in D:
        count[d] += 1
    if count[0] != 1:
        print(0)
    else:
        maxcount = max(count)
        S = 1
        for i in range(1, maxcount+1):
            S *= count[i-1]**count[i]
        M = int(S % 998244353)
        print(M)

Submission status: Accepted

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

#lines = stdin.readlines()
def rint():
    return map(int, sys.stdin.readline().split())

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())

N = oint()

d = list(rint())

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

d.sort()

if N > 1 and d[1] == 0:
    print(0)
    exit()

n = 1
c = 0
cprev = 1
ans = 1
for i in range(1, N):
    if d[i] == n:
        c+=1
    elif d[i] != n+1:
        print(0)
        exit()
    else:
        ans = (ans* pow(cprev, c, 998244353))%998244353
        n += 1
        cprev = c
        c = 1

ans = (ans* pow(cprev, c, 998244353))%998244353
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys
def read_a_integer():
    return int(sys.stdin.readline())

def read_a_list(dtype):
    return list(map(dtype, sys.stdin.readline().split()))


def main():
    N = read_a_integer()
    D = read_a_list(int)
    if D[0] != 0:
        print(0)
        return
    counter = collections.Counter(D)
    if counter[0] != 1:
        print(0)
        return
    max_D = max(D)
    ans = 1
    for i in range(2, max_D + 1):
        if i not in counter:
            print(0)
            return
        ans = (ans * (counter[i-1] ** counter[i])) % 998244353
    print(ans)
    # brute_force(N, D)

        


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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

n = int(input())
d = list(map(int, input().split()))
D = {i:[] for i in range(max(d)+1)}
if sum(d) == 0 and n != 1:
  print(0)
  exit()
for i in range(n):
  if i == 0 and d[i] != 0:
    print(0)
    exit()
  if i != 0 and d[i] == 0:
    print(0)
    exit()
  D[d[i]] += [i]
ans = 1

for i in range(max(d)):
  a = modpow(len(D[i]), len(D[i+1]), 998244353)
  ans = ans * a % 998244353

print(ans % 998244353)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = list(map(int,input().split()))
longest = max(D)
c = collections.Counter(D)
ans = 1
if c[0] > 1 or D[0] != 0:
    print(0)
else:
    for i in range(longest):
        if c[0] > 1:
            ans = 0
            break
        ans = ans * (c[i])**(c[i+1]) % 998244353
    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:
def answer():
    N = int(input())
    distances = list(map(int, input().split()))

    result = 1
    mod = 998244353

    if distances[0] != 0:
        result = 0
    elif 0 in distances[1:]:
        result = 0
    else:
        distances.sort()
        maximum = distances[-1]
        counts = [0] * (maximum + 1)
        counts[0] = 1
        for d in distances[1:]:
            counts[d] += 1
            result *= counts[d-1]
            result %= mod

    print(result)


if __name__ == '__main__':
    answer()

Submission status: Accepted

Solution code:
MOD = 998244353

n = int(input())
distances = list(map(lambda x: int(x), input().split()))

# 最初が0であることを確認
canSolve = True
ans = 1

if distances[0] != 0:
    canSolve = False
    ans = 0

dist_list = {}
if canSolve:
    for i in distances:
        if i in dist_list.keys():
            dist_list[i] += 1
        else:
            dist_list[i] = 1
            
            
    keys = list(dist_list.keys())
    keys.sort()
    keys.reverse()
    bigger = None
    smaller = None
    pre_v = None
    for v in keys:
        if bigger is None:
            bigger = dist_list[v]
            pre_v = v
            continue
        elif smaller is None:
            smaller = dist_list[v]
        else:
            bigger = smaller
            smaller = dist_list[v]
        
        if v==0 and smaller > 1:
            ans = 0

        if v == pre_v - 1:
            ans *= (smaller**bigger)
            ans = ans % MOD
            pre_v = v
        else:
            ans = 0
        
print(ans)

Submission status: Accepted

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

mod=998244353
c=collections.Counter(D)

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

Submission status: Accepted

Solution code:
import sys

pre_strk = 1
now_strk = 1
ans = 1
n = int(input())
d_list = list(map(int,input().split()))
# print(d_list)
if d_list[0] != 0:
    print(0)
    sys.exit()

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

for i in range(1,n):
    if d_list[i] == d_list[i-1]:
        now_strk += 1

    elif d_list[i] > d_list[i-1] + 1:
        print(0)
        sys.exit()

    elif d_list[i] != d_list[i-1] and d_list[i-1] != 1:
        for j in range(now_strk):
            ans *= pre_strk
        pre_strk = now_strk
        now_strk = 1
        # print(ans)
        ans = ans % 998244353

    else:
        pre_strk = now_strk
        now_strk = 1
for i in range(now_strk):
    ans *= pre_strk
print(ans%998244353)

Submission status: Accepted

Solution code:
n = int(input())
ls = list(map(int, input().split(' ')))
m = max(set(ls))
d = {}
for l in ls:
    d[l] = d.get(l, 0) + 1
ans = 0 if (ls[0] != 0 or d.get(0) >= 2) else 1
for i in range(1, m+1):
    if i not in d:
        ans = 0
    ans = (ans * (d.get(i-1, 0) ** d.get(i, 0))) % 998244353 
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
D = [int(x) for x in input().split()]
D_counter = Counter(D)
ans = 1

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

for d in D_counter:
    if d - 1 in D_counter:
        ans *= (D_counter[d - 1] ** D_counter[d]) % 998244353
        ans = ans % 998244353
    else:
        if not d == 0:
            print(0)
            sys.exit()
print(ans)