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 sys

N=int(input())

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

a=[0 for i in range(N)]
for i in range(N):
    a[x[i]]+=1

if x[0]!=0 or a[0]!=1: print(0),sys.exit()
for i in range(2,N):
    if a[i-1]==0 and a[i]!=0: print(0),sys.exit()

ans=1
for i in range(1,N):
    ans=(ans*a[x[i]-1])%998244353

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
D = list(map(int, input().split()))

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

div = 998244353

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

maxD = max(D)
res = 1
for i in range(1, maxD):
    res *= (c[i]**c[i+1])
    res %= div

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
mlmis = lambda: [-int(x) for x in input().split()]
INF = float('inf')
#

def main():
    N = ii()
    D = lmis()
    if (D[0] > 1) or (0 in D[1:]):
        print(0)
        return
    L = [0] * (max(D)+1)
    for d in D:
        L[d] += 1
    ans = 1
    for i in range(1, len(L)):
        ans *= (L[i-1]%998244353) ** L[i]
        ans %= 998244353
    print(ans)





main()

Submission status: Accepted

Solution code:
import math
import sys
MOD = 998244353

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

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

T = [0] * N

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

for i in range(1, N):
    if T[i] > 0 and T[i-1] == 0:
        print(0)
        sys.exit(0)

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

ans = 1
for i in range(2, N):
    if T[i] == 0:
        break
    # ans = (ans * int(math.pow(T[i-1], T[i])) % MOD
    ans = (ans * (T[i-1] ** T[i])) % MOD

print(ans)

Submission status: Accepted

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

if D[0] != 0 or N_cnt[0] != 1:
    print(0)
else:
    res = 1
    for i in range(1, N):
        res *= N_cnt[i - 1]**N_cnt[i]
        res %= MOD
    print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

MOD = 998244353
N = int(input())
D = list(map(int,input().split()))
maxD = 0
count = [0 for _ in range(N)]
for d in D:
    maxD = max(maxD,d)
    count[d] += 1
answer = 1
for i in range(maxD):
    x = count[i]
    y = count[i+1]
    answer *= pow(x,y,MOD)
    answer %= MOD
if count[0] != 1 or D[0] != 0:
    print(0)
else:
    print(answer)

Submission status: Accepted

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

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

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

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

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

    ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(D)
ans = 0
if D[0] == 0 and c[0] == 1:
    ans = 1
    M = max(D)
    for i in range(1, M + 1):
        if c[i] == 0:
            ans = 0
            break
        ans *= c[i - 1] ** c[i]
        ans %= 998244353
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

zero_id = []
for i in range(len(d)):
    if d[i] == 0:
        zero_id.append(i)
if zero_id == [0]:
    from collections import Counter
    c = Counter(d)
    keys = sorted(c.keys())

    ans = 1
    for i in range(keys[-1]):
        ans *= c.get(i, 0) ** c.get(i+1, 0)
    print(ans % 998244353)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    MOD = 998244353
    N = int(input())
    D = list(map(int, input().split()))

    c = Counter(D)

    if D[0] != 0 or c[0] != 1:
        return 0
    
    ans = 1
    m = max(D)
    for i in range(2, m+1):
        ans *= pow(c[i-1], c[i], MOD)
        ans %= MOD

    return ans

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

Submission status: Accepted

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

def readInts():
  return [int(s) for s in input().split(" ")]

MOD = 998244353

def solve(N, D):
  D1 = D[0]
  D = D[1:]

  if D1 != 0:
    return 0

  D.sort()

  ans = 1
  prev = 0
  prevCount = 1
  cur = 0
  while cur < len(D):
    c = 0
    while cur < len(D) and D[cur] == (prev + 1):
      cur += 1
      c += 1
    if c == 0:
      return 0

    ans *= (prevCount ** c) % MOD
    ans %= MOD
    prev += 1
    prevCount = c

  return ans

def main():
  N = readInts()[0]
  D = readInts()
  print(solve(N, D))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
n=int(input())
d=list(map(int,input().split()))
mod=998244353
if d[0]!=0:
    print(0)
    quit()
d.sort()

if d[1]==0:
    print(0)
    quit()
ans=1
last=1
now=1
cnt=0
i=1
while(i<n):
    if now==d[i]:
        cnt+=1
    elif now+1==d[i]:
        if cnt==0:
            print(0)
            quit()
        ans*=pow(last,cnt)
        ans=ans%mod
        last=cnt
        now=d[i]
        cnt=1
    else:
        print(0)
        quit()
    i+=1
if cnt>0:
    ans*=pow(last,cnt)
print(ans%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
MOD = 998244353
N = int(input())
D = inpl()
n = defaultdict(int)
M = 0
for i in range(N):
    m = D[i]
    n[m] += 1
    if m > M:
        M = m
if D[0] > 0 or n[0] > 1:
    print(0)
    exit()
ans = 1
for i in range(1,M+1):
    ans *= pow(n[i-1],n[i],MOD)
    ans %= MOD
    if ans == 0:
        break
print(ans)

Submission status: Accepted

Solution code:
import math
import collections
def modpow(a,b,MOD):#a**b(MOD)
    if b == 0:
        return 1
    if b%2:
        return a*modpow(a**2%MOD,b//2,MOD)%MOD
    else:
        return modpow(a**2%MOD,b//2,MOD)
MOD=998244353
n=int(input())
l=list(map(int,input().split()))
if l[0]!=0:
    print(0)
    exit()
else:
    l=l[1:]
if 0 in l:
    print(0)
    exit()
cl=collections.Counter(l)
ans=1
tmp=1
for i in range(1,max(l)+1):
    c=cl[i]
    if c==0:
        print(0)
        exit()
    ans*=modpow(tmp,c,MOD)
    ans%=MOD
    tmp=c
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N, *D = map(int, open(0).read().split())
MOD = 998244353

ctr = Counter(D)
ans = 1
for i in range(1, max(ctr) + 1):
    ans = ans * ctr[i - 1] ** ctr[i] % MOD

if ctr[0] == 1 and D[0] == 0:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

p = 998244353

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

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

C = [0] * n

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

flag = False

for c in C:
    if flag and c != 0:
        print(0)
        exit()
    if c == 0:
        flag = True
    

ans = 1

for i in range(1, n):
    ans *= pow(C[i - 1], C[i], p)
    ans %= p

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#eps=10**(-10)
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
#show_flg=True


mo=998244353

n=I()
d=LI()
dp=[0]*(1+n)
ans=1
if d[0]!=0:
    ans=0
if d.count(0)!=1:
    ans=0
m=0

for i in d:
    dp[i]+=1
    m=max(i,m)

for i in range(m):
    pt=pow(dp[i],dp[i+1],mo)
    ans*=pt
    ans%=mo


print(ans%mo)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    D = map(int, input().split())
    E = [[] for i in range(N)]
    for i,d in enumerate(D):
        E[d].append(i)

    if [0] != E[0]:
        return '0'
    res = 1
    e_ = E[0]
    for i,e in enumerate(E[1:], start=1):
        if e:
            res *= len(e_)**len(e)
            e_ = e
        else:
            if any(E[i+1:]):
                return '0'
            else:
                return str(res%998244353)
    return str(res%998244353)

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

Submission status: Accepted

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

N_MOD = 998244353

Dmax = max(D)
levels = [0] * (Dmax + 1)
#
for Di in D:
    levels[Di] += 1
#
if levels[0] != 1:
    print(0)
elif D[0] != 0:
    print(0)
else:
    ans = 1
    for i in range(1, Dmax + 1):
        p = levels[i - 1]
        i_p = levels[i]
        # print("#", p, i_p)
        for i in range(i_p):
            ans = (ans * (p % N_MOD)) % N_MOD
    #
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d_list = [ int(v) for v in input().split() ]
depth_list = [ 0 for i in range(n) ]
for i in d_list:
    depth_list[i] += 1


ld = len(depth_list)

ans = 1
mod = 998244353

if d_list[0] != 0:
    ans = 0
if depth_list[0] > 1:
    ans = 0
else:
    for i in range(1,ld-1):
        if depth_list[i] == 0 and depth_list[i+1] > 0:
            ans = 0

if ans != 0:
    for i in range(ld-1):
        ans *= pow(depth_list[i],depth_list[i+1],mod)
        ans %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

from collections import Counter
def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n = ri()
    ld = rli()
    if ld[0] != 0:
        print(0)
        return
    counter = Counter()
    for d in ld:
        counter[d] += 1
    cnt = 0
    ans = 1
    bef = 1
    be = -1
    for e, c in sorted(counter.items()):
        if e-be > 1:
            print(0)
            return
        if e == 0 and c > 1:
            print(0)
            return
        ans *= pow(bef, c)
        ans %= 998244353
        cnt += c
        # print(be, e, c, pow(bef, c))
        be = e
        bef = c
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 998244353

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

M = max(D)
T = [0] * (M + 1)

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

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

for i in range(1, M):
  if T[i] == 0:
    print(0)
    exit()

ans = 1
for i in range(2, M + 1):
  ans = ans * (T[i - 1] ** T[i]) % MOD

print(ans)

Submission status: Accepted

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

ans = 1
c = [0]*N
for i in range(N):
    c[D[i]] += 1
    if i != 0 and D[i] == 0:
        ans = 0


if len(set(D)) != max(D)+1:
    ans = 0
for i in range(1,N-1):
    ans *= pow(c[i],c[i+1],mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

MOD = 998244353

def repeatSquares(x, n):  # x^n
    res = 1
    while n != 0:
        if n % 2 == 1:
            res *= x
            res %= MOD  # MOD演算ないなら消していい
        x *= x
        n //= 2
        x %= MOD      # MOD演算ないなら消していい
    return res

N = int(input())
D = [0] + list(map(int, input().split()))

ans = 0
if D[1] == 0:
    D = D[2:]
    D.sort()
    
    ans = 1
    
    now = 1
    preCnt = 1
    cnt = 0
    for e in D:
        if e == now:
            cnt += 1
        else:
            ans *= repeatSquares(preCnt, cnt)
            ans %= MOD

            preCnt = cnt
            
            cnt = 1
            now += 1
            if now != e:
                ans = 0
                break

    ans *= repeatSquares(preCnt, cnt)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n = ni()
d = list(li())

mod = 998244353
dcnt = Counter(d)

# 正常か判断
def judge(n, d, dcnt):
    # 頂点1が0でないならNG
    for i in range(n):
        if i == 0 and d[i] != 0:
            return False
        if i > 0 and d[i] == 0:
            return False

    # keyが連続でなければNG
    dcnt_keys = sorted(list((dcnt.keys())))
    for i in range(len(dcnt_keys) - 1):
        if dcnt_keys[i+1] - dcnt_keys[i] != 1:
            return False

    return True

# dp
def dp(dcnt, mod):
    maxdepth = max(dcnt.keys())
    dp = [0]*(maxdepth+1)
    dp[0] = 1
    for depth in range(1, maxdepth+1):
        dp[depth] = dp[depth-1] * pow(dcnt[depth-1], dcnt[depth], mod)
        dp[depth] %= mod

    return dp[maxdepth]

if judge(n, d, dcnt):
    print(dp(dcnt, mod))
else:
    print(0)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    d = list(map(int,input().split()))
    d0 = d[0]
    d = sorted(d)
    l = [0]*(d[-1]+1)
    for i in d:
        l[i] += 1
    ans = 0
    if (not 0 in l) and d[1] > 0 and d0 == 0:
        ans = 1
        for i in range(1,len(l)):
            ans = ans*(l[i-1]**l[i])%998244353
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

mod = 998244353

n = int(input())
d = list(map(int, input().split()))
c = Counter(d)
if not(c[0] == 1 and d[0] == 0):
    print(0)
    exit()

k = sorted(c.keys())
prev = -1
ans = 1
for ki in k:
    if prev+1 != ki:
        ans = 0
        break
    a = c[ki-1] if ki != 0 else 1
    ans *= pow(a, c[ki], mod)
    ans %= mod
    prev = ki
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline

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

if d[0] > 0:
  print(0)
  exit(0)
e = dd(int)
e[0] = 1
for i in range(1, N):
  if d[i] == 0:
    print(0)
    exit(0)
  e[d[i]] += 1
res = 1
for k in range(1, max(e.keys()) + 1):
  res *= pow(e[k - 1], e[k], mod)
  res %= mod
  #print(res)
print(res % mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

MOD = 998244353

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

if Ds[0] != 0 or min(Ds[1:]) == 0:
    print(0)
    sys.exit()

cnt = Counter(Ds)

ans = 1
for d in range(1, max(Ds)+1):
    if cnt[d] == 0:
        ans = 0
        break
    ans *= pow(cnt[d-1], cnt[d], MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod =  998244353
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=10**6):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))
def main():
    N=I()
    D=LI()
    if D[0]!=0:
        print(0)
        exit()
    ans = ModInt(1)
    
    cnt = [0]*N
    for i,d in enumerate(D):
        cnt[d]+=1

    for i,c in enumerate(cnt[1:],start=1):
        if cnt[i-1]==0 and c!=0:
            print(0)
            exit()
        if c==0 and cnt[i-1]==0:
            continue

        ans *= pow(cnt[i-1],c)


    if cnt[0]>1:
        print(0)
        exit()
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n = ii()
    d = li()

    if not  d[0] == 0:
        print(0)
        exit()
    else:
        cnt = [0 for i in range(n+1)]
        for i in d:
            cnt[i]+=1
        if not cnt[0] == 1:
            print(0)
            exit()
        for i in range(1,n):
            if cnt[i-1] == 0 and (not cnt[i] ==0):
                print(0)
                exit()
        ans = 1
        for i in range(1,n):
            if cnt[i] == 0:
                break
            
            ans = (ans*(cnt[i-1]**cnt[i]))%998244353

        print(ans)


main()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

pat = 1
for i in range(1,max(D)+1):
    if C[i] == 0:
        print(0)
        exit()
    for _ in range(C[i]):
        pat *= C[i-1]
        pat %= 998244353

print(pat)

Submission status: Accepted

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

def po(hiki, rui):
    so = 1
    for i in range(rui):
        so = (so*hiki)%998244353
    return so

max_d = 0
for i in range(n):
    if max_d < d[i]:
        max_d = d[i]


m = [0 for i in range(10**5)]

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

#失敗判定
sip = 0
for i in range(1,max_d+1):
    if m[i] == 0:
        sip = 1
if d[0] != 0:
    sip = 1
if m[0] > 1:
    sip = 1

if sip:
    print(0)
else:
    ans = 1
    for i in range(1,max_d + 1):
        kop = po(m[i-1],m[i])
        ans = (ans * kop)%998244353
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

MOD = 998244353
N= int(input())
D = inpl()
C = Counter(D)

if (D[0] != 0) or (C[0] != 1):
    print(0)
else:
    M = max(C.keys())
    ans = 1
    for i in range(M):
        ans = ans * pow(C[i], C[i+1], MOD) % MOD
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = list(map(int,input().split()))
output = 1
cnt = [0]*N
flag = 0

if D[0]!=0:
    flag = 1

for i in range(1,N):
    cnt[D[i]-1]+=1
    if D[i]==0:
        flag = 1

if flag != 1:
    for i in range(1,len(cnt)):
        # if cnt[i]==0:
        #     continue
        for j in range(cnt[i]):
            output *= cnt[i-1]
            output = output%998244353

if flag == 1:
    output = 0
print(output)

Submission status: Accepted

Solution code:
class mod_comb_perm:
    def __init__(self,n,mod):
        self.mod = mod
        self.fact = [1 for i in range(n)]
        for i in range(2,n+1):
            self.fact[i-1] = (self.fact[i-2]*i)%mod

    def expo(self,x,n):
        if n == 2:
            return (x * x) % self.mod
        elif n == 1:
            return  x%self.mod
        elif n == 0:
            return 1
        elif n % 2 == 1:
            return (self.expo(x, n - 1) * x) % self.mod
        else:
            temp = self.expo(x, n // 2) % self.mod
            return (temp * temp) % self.mod
    def comb(self,n,k):
        a = (self.fact[n]*self.expo(self.fact[k],self.mod-2))%self.mod
        return (a*self.expo(self.fact[n-k],self.mod-2))%self.mod
    def invm(self,x):
        return (self.expo(self.fact[x],self.mod-2))%self.mod
    def perm(self,n,k):
        return (self.fact[n]*self.expo(self.fact[n-k],self.mod-2))%self.mod



n = int(input())

mcp = mod_comb_perm(n+1,998244353)

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

flag = True
buf = [0 for i in range(n + 1)]

for i in range(n):
    if i == 0:
        if arr[i] != 0:
            flag = False
            break
    else:
        if arr[i] == 0:
            flag = False
            break
    buf[arr[i]] += 1

if flag:
    ans = 1
    bef = 1
    has_zero = False
    for i in range(1,n+1):
        if buf[i] == 0:
            has_zero = True
            continue

        if has_zero:
            if buf[i] != 0:
                flag = False
                break
        else:
            ans = ans*mcp.expo(bef,buf[i])
            ans %= 998244353

        bef = buf[i]

    if flag:
        print(ans)
    else:
        print(0)

else:
    print(0)

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()))
from collections import Counter
# import math
MOD = 998244353

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    items = sorted(cnt.items(), key=lambda x: x[0])
    # print(items)
    if nums[0] != 0:
        print(0)
        return

    ans = 1
    prev = 1
    for i, item in enumerate(items):
        if i != item[0]:
            print(0)
            return
        if item[0] == 0 and item[1] != 1:
            print(0)
            return
        else:
            # a,b = max(item[1], prev), min(item[1], prev)
            ans *= (prev**item[1])
            prev = item[1]
            ans %= MOD


    print(ans)
if __name__ == "__main__":
    main()

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

d.sort()
ma = d[-1]

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

ans = 1
pre = 1
for i in range(ma+1):
    if c[i] == 0:
        print(0)
        exit()
    ans *= pow(pre, c[i], mod)
    ans %= mod
    pre = c[i]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
D = [int(i) for i in input().split()]
count = [0]*N
max_n = 0

for elem in D:
    count[elem] += 1
    if elem > max_n:
        max_n=elem

ans=1
if count[0] == 1 and D[0] == 0:
    for i in range(1,max_n+1):
        ans = (ans*((count[i-1])**count[i]))%998244353
else:
    ans = 0

print(ans%998244353)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

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

a.sort()

a = s(a)
count = 1

for i in range(1,len(a)):
    if i == 1 and a[i-1][1] != 1:
        print(0)
        exit()
    if a[i][0]-1 != a[i-1][0]:
        print(0)
        exit()
    count *= (pow(a[i-1][1],a[i][1]))%998244353  
    count %= 998244353
print(count)

Submission status: Accepted

Solution code:
n=int(input())
L=[int(i) for i in input().split()]
A=[0 for i in range(n)]
mod=998244353

for num in L:
    
    A[num]+=1

if A[0]!=1 or L[0]!=0:
    print(0)
else:
    ans=1
    for i in range(n-1):
        ans*=A[i]**A[i+1]
        ans=ans%mod
    print(ans%mod)

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()
for i in range(n-1):
  if d[i+1]-d[i]>=2:
    print(0)
    sys.exit()
x=1
ct=0
ctb=1
ans=1
mod=998244353
for i in range(1,n):
  if d[i]==x:
    ct+=1
  else:
    if x!=1:
      for j in range(ct):
        ans*=ctb
        ans%=mod
    ctb=ct
    ct=1
    x+=1
for i in range(ct):
  ans*=ctb
  ans%=mod
print(ans%mod)

Submission status: Accepted

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

mod = 998244353

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

from collections import Counter

counter = Counter(d_list)

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

prev = 0
max_d = max(d_list)
ans = 1
for i in range(1, max_d + 1):
    if i == 1:
        if counter[i] != 0:
            ans = 1
        else:
            print(0)
            exit()
    else:
        if counter[i] != 0:
            ans *= prev ** counter[i]
            ans %= mod
        else:
            print(0)
            exit()
    prev = counter[i]

print(ans)

Submission status: Accepted

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

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

#print(count[:10])

ans = 1
inf = 998244353

for i in range(len(count)):
    if i == 0:
        pass
    else:
        tmp = pow(count[i-1], count[i], inf)
        ans *= tmp
        ans %= inf

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

print(ans)

Submission status: Accepted

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


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

if D.count(0) != 1:
    print(0)
    exit()


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


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

    ans *= X[d - 1]
    ans %= MOD

print(ans)

Submission status: Accepted

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

cnt = [0]*100100
for d in D:
    cnt[d] += 1
ans = int(D[0]==0 and cnt[0]==1)

check = 1
for i,c in enumerate(cnt[1:],1):
    if c == 0: break
    c0 = cnt[i-1]
    check += c
    ans *= pow(c0,c,mod)
    ans %= mod
if check != N:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
mod = 998244353
ans = 1

def pow(x, y):
    m = x
    ans = 1
    while y != 0:
        if y % 2 == 1:
            ans = (ans * m) % mod
        m = (m*m)% mod
        y //= 2
    return ans
# print(A)
# print(pow(3,4))
import sys
if A[0] != 0:
    print(0)
else:
    B = [0] * (max(A)+1)
    for i in range(n):
        # print("i",i)
        B[A[i]] += 1
    # print(B)
    if B[0] != 1:
        print(0)
        sys.exit()
    for i in range(len(B)-1):
        ans = (ans * pow(B[i], B[i+1])) % mod
    print(ans)