Problem:


Score : 300 points

Problem Statement

Given is an integer sequence D_1,...,D_N of N elements. Find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition:

For every integer i from 1 to N, the distance between Vertex 1 and Vertex i is D_i.

Notes

A tree of N vertices is a connected undirected graph with N vertices and N-1 edges, and the distance between two vertices are the number of edges in the shortest path between them.

Two trees are considered different if and only if there are two vertices x and y such that there is an edge between x and y in one of those trees and not in the other.

Constraints

1 \leq N \leq 10^5

0 \leq D_i \leq N-1

Input

Input is given from Standard Input in the following format:

N
D_1 D_2 ... D_N

Output

Print the answer.

Sample Input 1

4
0 1 1 2

Sample Output 1

2

For example, a tree with edges (1,2), (1,3), and (2,4) satisfies the condition.

Sample Input 2

4
1 1 1 1

Sample Output 2

0

Sample Input 3

7
0 3 2 1 2 2 1

Sample Output 3

24



Sample input:
4
0 1 1 2


Sample output:
2

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, arr):
    if arr[0] != 0:
        return 0

    c = Counter(arr)

    if c[0] != 1:
        return 0
    max_c = max(c)
    for i in range(max_c + 1):
        if i not in c:
            return 0

    c = list(c.items())
    c.sort()

    prev = 1
    ans = 1
    mod = 998244353

    for _, i in c[1:]:
        ans *= pow(prev, i) % mod
        ans %= mod
        prev = i

    return ans


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

print(solve(n, arr))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

N = getN()
D = getList()
if D[0] != 0:
    print(0)
    exit()
D = Counter(D)
D = sorted(D.items(), key = lambda x: x[0])
if D[0][1] != 1:
    print(0)
    exit()

x1 = 0
y1 = 1
ans = 1
for i in D[1:]:
    if x1 + 1 != i[0]:
        ans = 0
        break
    ans *= y1 ** i[1]
    x1 = i[0]
    y1 = i[1]
print(ans % 998244353)

Submission status: Accepted

Solution code:
n,*d=map(int,open(0).read().split())
mod=998244353
c=[0]*(max(d)+1)
for i in d:
  c[i]+=1
ans=1
if (not c[0]==1) or (not d[0]==0):
  print(0)
  exit()
for i in range(max(d)):
  ans*=pow(c[i],c[i+1],mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d_list = list(map(int,input().split()))
p = 998244353
import collections
result = 0
check = True
for i in range(1,len(d_list)):
  if d_list[i] == 0:
    check = False
 
if d_list[0] != 0:
  print(result)
elif check == False:
  print(result)
else:
  result = 0
  c = collections.Counter(d_list)
  for i in range(1,max(d_list) + 1):
    if i == 1:
      result += 1
    elif  c[i] == 0:
        result = 0
    else:
      result = result * (c[i -1] ** c[i])

  print(result % p)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N=I()
    D=LI()
    L=[0]*N
    N2=max(D)

    
    for i in range(N):
        L[D[i]]+=1
    prev=1
    ans=1
    if D[0]!=0 or L[0]!=1:
        print(0)
    else:
        for i in range(1,N2+1):
            now=L[i]
            ans=(ans*pow(prev,now,mod))%mod
            prev=now
            
        print(ans)
            
        
    

main()

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 998244353

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

d_count = Counter(d)

ans = 1
pre_count = 1

if d[0] > 0: ans = 0

for i,(dist,count) in enumerate(sorted(d_count.items())):
    if i != dist or (i==0 and count > 1):
        ans = 0
        break
    
    ans *= pow(pre_count,count,MOD)
    ans %= MOD
    
    pre_count = count
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

MOD = 998244353

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

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
d = list(map(int,input().split()))
if d[0]!=0 or d[1:].count(0)!=0:
  print(0)
  exit()
l = [0 for i in range(n)]
for i in d:
  l[i] += 1
cou = 1
if 0 in l:
  a = l.index(0)
  if sum(l[a:])!=0:
    print(0)
    exit()
for i in range(n-2):
  if l[i+1]!=0:
    a = l[i]
    b = l[i+1]
    cou *= (a**b)%mod
print(cou%mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n = int(input())
D = list(map(int,input().split()))
if D[0] != 0 or D.count(0) != 1:
    print(0)
    sys.exit()
D = Counter(D)
L = sorted(D.items())
pk = 0
pv = 1
ans = 1
for i,j in L:
    if i == 0:
        continue
    if i != pk+1:
        print(0)
        break
    ans *= pv**j
    ans %= 998244353
    pk = i
    pv = j
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = [int(x) for x in input().split()]
mod = 998244353
m = [0]*n

for x in d:
    m[x] += 1
ans = 1

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

Submission status: Accepted

Solution code:
MOD = 998244353
n = int(input())
d = list(map(int, input().split()))
dist_map = [0]*n
for dist in d:
    dist_map[dist] += 1
ans = 1

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

for i in range(1, n):
    ans *= pow(dist_map[i-1], dist_map[i], MOD)
    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)
 
if d[0] != 0 or c[0] != 1:
    print(0)
    exit()
 
ans = 1
for i in range(1, max(d)+1):
    if i not in c:
        print(0)
        exit()
    ans *= pow(c[i-1], c[i], mod)
 
print(ans % mod)

Submission status: Accepted

Solution code:
def m():
    MOD = 998244353
    N = int(input())
    D = [0] + list(map(int, input().split()))
    if D[1] != 0:
        return 0
    tree = {1:1}
    for i in range(2, N + 1):
        if D[i] == 0: return 0
        tree[D[i] + 1] = tree[D[i] + 1] + 1 if tree.get(D[i] + 1, False) else 1

    height = len(tree.keys())+1
    cnt = 1
    for i in range(2, height):
        if not tree.get(i, 0):
            return 0
        cnt = cnt * pow(tree[i-1], tree[i]) % MOD
    return cnt


print(m())

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline
MOD = 998244353

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

    if D[0] != 0:
        print(0)
        return
    
    D.sort()
    Dmax = max(D)
    Ditems = collections.Counter(D).items()
    Dcount = list(zip(*Ditems))

    Dset = set(Dcount[0])
    if Dset != set(range(Dmax+1)):
        print(0)
        return

    if Dcount[1][0] != 1:
        print(0)
        return

    ans = 1
    for i in range(2, Dmax+1):
        ans *= pow(Dcount[1][i-1], Dcount[1][i], MOD)
        ans %= MOD

    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
MOD = 998244353

n = int(input())
d = [int(_) for _ in input().split()]

ans = 1
if d[0] != 0:
    ans = 0
else:
    D = sorted(collections.Counter(d).most_common())
    if D[0][1] != 1:
        ans = 0
    else:
        cnt = 0
        prev = 1
        for i in D:
            if i[0] == cnt:
                ans = ans * pow(prev, i[1], MOD) % MOD
                prev = i[1]
            else:
                ans = 0
                break
            cnt += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# from collections import defaultdict, deque
# from math import sqrt, gcd, factorial, tan, pi, sin, cos
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1]

MOD = 998244353

def solve():
    n = int(input())
    d = [int(x) for x in input().split()]
    f = [0] * n
    for e in d:
        f[e] += 1
    
    ok = f[0] == 1 and d[0] == 0
    z = 0
    ans = 1
    for i in range(1, n):
        if (f[i] == 0): z = 1
        if (z and f[i]): ok = 0
        ans *= pow(f[i-1], f[i], MOD)
        ans %= MOD
    print(ans * ok)




t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()



"""
1 -> (1, 2) -> (2 ** 3, 3) -> (3, 1)

"""

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
MOD = 998244353
N = int(input())
D = list(map(int,input().split()))
d = defaultdict(int)
for i in D:
    d[i] += 1
ans = 1
if d[0] != 1 or D[0] != 0:
    print(0)
else:
    for i in range(1,N):
        ans = ans*pow(d[i-1],d[i],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()

c = {}
for i in D:
    c.setdefault(i, 0)
    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 *= pow(c[i - 1], c[i], 998244353)
    result %= 998244353
print(result)

Submission status: Accepted

Solution code:
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 *= pow(c[i - 1], c[i], 998244353)
    result %= 998244353
print(result)

Submission status: Accepted

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

import collections
c = collections.Counter(li)

#print(c)
# Counter({'a': 4, 'c': 2, 'b': 1})
#print(c.items())
# dict_items([('a', 4), ('b', 1), ('c', 2)])

tmp = c.items()
cnt = list(tmp)
cnt.sort()
#print(cnt)
#[(0, 1), (1, 2), (2, 3), (3, 1)]
ans = 1
for i,c in enumerate(cnt):
    if i == 0:
        if c[1]>=2:
            print(0)
            exit()
        continue
    if c[0]!= i:
        print(0)
        exit()
    #print(cnt[i-1][1],c[1])
    ans *= cnt[i-1][1]**c[1]
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(d)

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

ans = 1
for i in range(1, max(d)+1):
    if i not in c:
        print(0)
        exit()
    ans *= pow(c[i-1], c[i], mod)

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
D = list(map(int, sys.stdin.readline().rsplit()))
C = Counter(D)
mod = 998244353

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

res = 1
for i in range(1, max(D) + 1):
    if i not in C:
        print(0)
        exit()
    res *= (C[i - 1] ** C[i]) % mod

print(res % mod)

Submission status: Accepted

Solution code:
import sys

# import re
# import math
import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
MOD2 = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    d = na()

    c = collections.Counter(d)
    lim = max(c)

    flg = False
    if d[0] != 0:
        flg = True

    if c[0] != 1:
        flg = True

    for i in range(lim + 1):
        if i not in c.keys():
            flg = True
            break

    if flg:
        print(0)
        exit(0)

    ans = 1
    for i in range(2, lim + 1):
        ans *= pow(c[i - 1], c[i], MOD2)
        ans %= MOD2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
MOD = 998244353
dmax = max(d)
dmin = min(d[1:])
cnt = [0] * n
for i, dd in enumerate(d):
    cnt[dd] += 1

if d[0] != 0 or dmin == 0:
    print(0)
    exit()
ans = 1
before = cnt[0]
for i in range(1,dmax+1):
    ans *= pow(before, cnt[i],MOD)
    before = cnt[i]
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
#MOD = 10 ** 9 + 7
MOD = 998244353
def main():
    N = int(readline())
    D = list(map(int, readline().split()))
    if D[0]!=0:
        print(0)
        exit()
    node = [0]*(max(D)+1)
    for i in range(N):
        node[D[i]] += 1
    if node[0]>1:
        print(0)
        exit()
    ans = 1
    for i in range(len(node)-1):
        ans *= node[i]**node[i+1]
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = [0]*(n+1)
for i in a:
  c[i] += 1
ans = 1
for i in range(n+1):
    if c[-1] == 0:
        c.pop()
    else:
        break

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

if a[0] != 0:
    ans *= 0
if c[0] != 1:
    ans *= 0
print(ans)

Submission status: Accepted

Solution code:

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

from collections import Counter
c=Counter(d)

mod=998244353
ans=1
key=set(c.keys())
if d[0]==0 and c[0]==1 and set(range(len(key))) == key:
    for i in range(len(key)):
        #print(i,c[i],c[i+1],c[i]**c[i+1])
        ans=ans*c[i]**c[i+1] %mod
else:
    ans=0
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
d = list(map(int,input().split()))
c = Counter(d)
mod=998244353
if d[0]==1:
    print(0)
else:
    D = 1
    for i in d[1:]:
        D = (D*c[i-1])%mod
    print(D)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
D = list(map(int, input().split()))
c = Counter(D)

total = 1
count = 0
for i in range(n):
  num = c.get(i, 0)
  if num == 0:
    total = 0
    break
  count += num
  if i == 0 and (c[i] != 1 or D[0] != 0):
    total = 0
  if i > 0:
    total = (total * (c[i - 1] ** c[i])) % 998244353
  if count == n:
    break
print(total)

Submission status: Accepted

Solution code:
mod = 998244353 
n= int(input())
d= list(map(int,input().split()))
if (d[0]!=0) or (0 in d[1:]):
    print(0)
    exit(0)
md=max(d)
def pf(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
tl=[0]*md
for c in d[1:]:tl[c-1]+=1
if 0 in tl:
    print(0)
    exit(0)
ans=1
for i in range(md-1):ans=(ans%mod*pf(tl[i],tl[i+1],mod))%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

mod = 998244353

def solve():
    N = int(input())
    Ds = list(map(int, input().split()))
    if Ds[0] != 0:
        print(0)
        return
    
    counter = Counter(Ds)
    ret = 1

    if counter[0] > 1:
        print(0)
        return
    max_key = max(counter.keys())
    for i in range(1, max_key+1):
        if i not in counter:
            # print(i,counter)
            print(0)
            return
        
        ret = (ret*(counter[i-1]**counter[i]))%mod
        # print(ret)
        
    print(ret)
    
solve()

Submission status: Accepted

Solution code:
from collections import Counter

def cal(D,M):
    C = Counter(D)
    MC = C.most_common()
    MC.sort(key = lambda x:x[0])
    n = len(MC)
    #頂点1が根じゃないときも連結の仕方を変えずに見方を変えることで
    #頂点1を根にできる.
    #従ってD[i-1]は頂点iの深さと見なせる
    for i in range(n):
        if MC[i][0] != i:
            #深さiと深さi-1又は深さiと深さi+1を繋げない
            return 0
    if MC[0][1] != 1 or D[0] != 0:
        #1以外の根がある又は1が根になってない
        return 0

    output = 1
    for i in range(n-1):
        output *= pow(MC[i][1],MC[i+1][1],M)
        output %= M
    return output

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

    ans = cal(D,M)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 998244353

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

class ModInt:
    def __init__(self, n=0, mod=mod):
        self.mod = mod
        self.n = n % self.mod
    
    def value(self):
        self.n %= self.mod
        return self.n
    
    def __add__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n + rhs.n, self.mod)
        return self.__class__(self.n + rhs, self.mod)
    
    __radd__ = __add__
    
    def __sub__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n - rhs.n, self.mod)
        return self.__class__(self.n - rhs, self.mod)
    
    def __rsub__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n - self.n, self.mod)
        return self.__class__(lhs - self.n, self.mod)

    def __mul__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n * rhs.n, self.mod)
        return self.__class__(self.n * rhs, self.mod)
    
    __rmul__ = __mul__

    def __floordiv__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n // rhs.n, self.mod)
        return self.__class__(self.n // rhs, self.mod)
    
    def __rfloordiv__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n // self.n, self.mod)
        return self.__class__(lhs // self.n, self.mod)

    def __iadd__(self, rhs):
        if isinstance(rhs, ModInt):
            self.n += rhs.n
        else:
            self.n += rhs
        if self.n >= self.mod:
            self.n -= self.mod
        
        return self
    
    def __isub__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        if self.n < rhs_n:
            self.n += self.mod
        self.n -= rhs_n
        return self
    
    def __imul__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        self.n = self.n * rhs_n % self.mod
        return self
    
    def __ifloordiv__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        exp = self.mod - 2
        while exp:
            if exp % 2:
                self *= rhs_n
            
            rhs_n *= rhs_n
            rhs_n %= self.mod
            exp //= 2
        
        return self
    
    def __pow__(self, exp):
        exp_n = exp.n if isinstance(exp, ModInt) else exp
        if exp_n == 0:
            return self.__class__(1, self.mod)
        if exp_n % 2 == 0:
            t = self.__pow__(exp_n // 2)
            return t * t
        return self * self.__pow__(exp_n - 1)
    
    def __str__(self):
        return str(self.value())


n = ni()
d = na()

dic = defaultdict(int)
max_d = 0
if d[0] >= 1:
    print(0)
    exit()

for i in range(n):
    dic[d[i]] += 1
    max_d = max(max_d, d[i])

if dic[0] != 1:
    print(0)
    exit()
ans = ModInt(1)
for i in range(1, max_d + 1):
    if dic[i] == 0:
        ans = 0
    ans *= ModInt(dic[i - 1]) ** dic[i]

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:
    c = collections.Counter(D)
    ans = 1
    for val in D[1:]:
        ans = (ans*c[val-1])%mod
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
*D, = map(int, input().split())
mod = 998244353
if D[0] != 0:
    print(0)
    exit()
C = {}
for d in D:
    try:
        C[d] += 1
    except BaseException:
        C[d] = 1
ans = 1
for d in D[1:]:
    try:
        ans = (ans * C[d - 1]) % mod
    except BaseException:
        ans = 0
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)
tmp = 1
ans = 1
zero_flg = False

for dist in range(N):
    if dist == 0 and (c[0] != 1 or D[0] != 0):
        print(0)
        exit()
    elif c[dist] == 0:
        zero_flg = True
    elif c[dist] > 0 and zero_flg:
        print(0)
        exit()
    else:
        ans *= pow(tmp, c[dist], MOD)
        ans %= MOD
        tmp = c[dist]

print(ans)

Submission status: Accepted

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

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

A = [0]*n

for i in range(n):
    A[D[i]] += 1

#print(A)

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

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

Submission status: Accepted

Solution code:
import collections
MOD = 998244353
def main():
    N = int(input())
    D = [int(_) for _ in input().split()]
    Dmax = max(D)
    cc = collections.Counter(D)
    if D[0] != 0: return 0
    if cc[0] != 1: return 0
    for i in range(Dmax+1):
        if cc[i] == 0: return 0
    output = 1
    for i in sorted(cc.keys()):
        if i in (0, 1): continue
        output *= pow(cc[i-1], cc[i], MOD)
        output %= MOD
    return output

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

Submission status: Accepted

Solution code:
mod=998244353
n=int(input())
from collections import Counter as co
j=list(map(int,input().split()))
l=co(j)
ll=len(l)
for i in range(ll):
    if i not in l:print(0);exit()
if l[0]>=2 or j[0]!=0:print(0);exit()
ans=1
pre=1
for k,v in sorted(l.items()):
    ans*=pow(pre,v,mod)
    ans%=mod
    pre=v
print(ans%mod)

Submission status: Accepted

Solution code:
def nikkei19q_b():
    _ = int(input())
    D = list(map(int, input().split()))
    div = 998244353

    dmax = max(D)
    cntr = [0] * (dmax + 1)
    for d in D: cntr[d] += 1  # カウンター

    if D[0] != 0: return 0  # 最初に入力される頂点1は距離0マスト
    if cntr[0] != 1: return 0  # 距離0が無い、または2つ以上、はおかしい

    ans = 1
    for i in range(1, dmax+1):
        if cntr[i] == 0: return 0  # カウント0だとつながらないのでNG
        ans = ans * (cntr[i-1] ** cntr[i]) % div
    return ans

print(nikkei19q_b())

Submission status: Accepted

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

M = max(D)
cnt = [0 for i in range(M + 1)]

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

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

res = 1
MOD = 998244353
for i in range(2, M + 1):
    res *= cnt[i - 1] ** cnt[i]
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = list(map(int, input().split()))
d = collections.Counter(D)
maxnum = max(D)
ans = 1
for i in range(maxnum+1):
    if i == 0:
        if D[0] != 0 or d.get(0,0) != 1:
            ans = 0
            break
    else:
        if d.get(i, 0) == 0:
            ans = 0
            break
        ans *= d[i-1]**d[i]

print(ans%998244353)

Submission status: Accepted

Solution code:
# import bisect
import unittest
from io import StringIO
# https://note.nkmk.me/python-scipy-connected-components/
from collections import Counter, deque
# from copy import copy, deepcopy
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    def main():
        n = int(input())
        D = list(map(int, input().split()))
        cnts=[0]*(max(D)+1)
        for i in D:
            cnts[i]+=1

        if cnts[0]!=1 or D[0]!=0: return 0
        ans=1

        for i in range(2,max(D)+1):
            if cnts[i]==0:
                return 0
            ans*=cnts[i-1]**cnts[i]

        return ans % 998244353

    print(main())

# 
resolve()

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    n = II()
    dd = MII()
    DIV = 998244353
    if dd[0] != 0:
        print(0)
        return None
    dist = [0]*n
    for d in dd:
        dist[d] += 1
    res = 1
    for d in dd[1:]:
        res *= dist[d-1]
        res %= DIV
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    d = list(map(int,input().split()))
    md = 998244353

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

    dp = [0]*n
    for i in d:
        dp[i]+=1
    res = 1
    for i in d[1:]:
        res = (res * dp[i-1]) % md
    print(res%md)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int,input().split()))
m = max(d)
if(d[0] != 0 or m >= n):
    print(0)
else:
    s = [0] * (m+1)
    for i in d:s[i] += 1
    if(0 in s or s[0] != 1):
        print(0)
    else:
        t = 1
        for i in range(1,m+1):
            t *= s[i-1]**s[i]
            t %= 998244353
        print(t)

Submission status: Accepted

Solution code:
MOD=998244353
from collections import Counter
N=int(input())
D=list(map(int,input().split()))
if D[0]!=0:
    print(0)
    exit()
c=sorted(Counter(D[1:]).most_common(),key=lambda x:x[0])
ans=1
for i in range(1,len(c)):
    if(c[i][0]!=i+1):
        print(0)
        exit()
    ans=(ans*pow(c[i-1][1],c[i][1],MOD))%MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

if __name__ == '__main__':
    MOD = 998244353
    n = int(input())
    d = list(map(int, input().split()))
    if d[0] != 0:
        print(0)
        exit(0)
    c = Counter(d)
    if c[0] != 1:
        print(0)
        exit(0)
    ans = 1
    for i in range(n - 1):
        ans *= pow(c[i], c[i + 1], MOD)
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
if d[0] != 0:
    print(0)
    exit()
d.sort()
if d[1] == 0:
    print(0)
    exit()
cnt = 1
pre = 1
ans =1
i = 1
mod = 998244353
while i < n:
    if d[i]-1 != d[i-1]:
        ans = 0
    while i!=n-1 and d[i+1] == d[i]:
        i+=1
        cnt+=1
    ans *= pow(pre,cnt,mod)
    ans %= mod
    pre =cnt
    cnt = 1
    i+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
mod = 998244353

n = int(input())
dl = list(map(int, input().split()))
c = Counter(dl)

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

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

res = 1
for x in range(max(dl)):
    res *= pow(c[x],c[x+1],mod)
    res %= mod

print(res)