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: Time Limit Exceeded

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

if D[0] != 0:
  print('0')
elif max(D) == 1:
  print('1')
else:
  for i in range(1, max(D)):
    answer *= D.count(i) ** D.count(i + 1)
  print(answer % 998244353)

Submission status: Time Limit Exceeded

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

if min(Ds)!=0 or Ds.count(0)!=1:
    print(0)
else:
    Ans=[0]*(max(Ds)+1)
    Ans[0]=1
    for i in range(1, max(Ds)+1):
        Ans[i]=(Ans[i-1]*(Ds.count(i-1)**Ds.count(i)))%998244353

    print(Ans[max(Ds)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = ( ans * ((prev**count) %998244353 ) ) %998244353
    prev = count
print(ans)

Submission status: Time Limit Exceeded

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

if D[0] != 0:
  print(0)
  exit()
  
max_distance = [i+1 for i in range(max(D))]
stock = 1
for i in max_distance:
  count_1 = D.count(i-1)
  count_2 = D.count(i)
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

ans=None

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

    mul=1
    n=1

    for i in range(1,max(D)+1):
        m=D.count(i)
        mul*=n**m
        n=m
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys


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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def power_mod(a, n, mod):
    a=a%mod
    if n==0:
        return 1
    elif n==1:
        return a
    elif n%2==0:
        return power_mod(a,n//2,mod)**2%mod
    else:
        return (power_mod(a,(n-1)//2,mod)**2%mod)*a%mod

N=int(input())
distances=list(map(int,input().split()))
maximum=max(distances)

if distances[0]!=0 or distances.count(0)>=2 or maximum>=N:
    print(0)
else:
    count_dist=list(distances.count(i) for i in range(maximum+1))
    if count_dist.count(0) >= 1:
        print(0)
    else:
        count=1
        for i in range(maximum):
            count = count*power_mod(count_dist[i],count_dist[i+1],998244353)%998244353
        print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = (ans * (prev**count) ) %998244353
    prev = count
print(ans)

Submission status: Time Limit Exceeded

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

if D[0] != 0 or D.count(0) != 1:
  print(0)
  exit()
  
max_distance = [i+1 for i in range(max(D))]
stock = 1
for i in max_distance:
  count_1 = D.count(i-1)
  count_2 = D.count(i)
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)

Submission status: Time Limit Exceeded

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

if d[0] != 0:
  print(0)
else:
  M = max(d) + 1
  num = [0] * M
  ans = 1
  for i in range(M):
    num[i] = d.count(i)
  for i in range(M-2):
    ans = ans * (num[i+1] ** num[i+2]) % 998244353
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = ans * (prev**count)
    prev = count
print(ans%998244353)

Submission status: Time Limit Exceeded

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

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

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

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

    tmp = 1
    ans = 1
    max_num = max(d)
    for i in range(1, max_num+1):
        if i+1 in d:
            count = d.index(i+1)
        elif i+1 == max_num+1:
            count = len(d)
        else:
            print('0')
            exit()
        ans *= tmp ** count
        ans %= mod
        tmp = count
        d = d[count:]

    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 1
#n1が0ではない、もしくは他に0がある
if D[0] != 0 or D.count(0) != 1:
  ans = 0
else:
  for i in range(1, max(D)):
    ans *= D.count(i) ** D.count(i + 1)
    if ans == 0:
      break
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
BIGMOD = 998244353

def modPow(x,n):
    ans = 1
    while n >= 1:
        if bin( n & 1)==bin(1):
            ans = (ans*x) % BIGMOD
        x = x * x % BIGMOD
        n = n>>1
    return ans % BIGMOD

def modFact(N):
    fact = []
    fact.append(1) #0! = 1
    for i in range(1,N+1):
        a = fact[i-1]*i % BIGMOD
        fact.append(a)
    return fact

def modInvFact(fact):
    invFact = []
    for i in range(1,N+2):
        a = modPow(fact[i-1],BIGMOD-2)
        invFact.append(a)
    return invFact

def modPlus(a,b):
    return (a + b) % BIGMOD

def modMinus(a,b):
    if a-b >= 0:
        return (a - b) % BIGMOD
    else:
        return (a - b + BIGMOD)
    
def modMulti(a,b):
    return a * b % BIGMOD

# fact(n),invFact(r),invFact(n-r)
def nCr(fact,invFact,n,r):
    return (fact[n] * invFact[r] * invFact[n-r] ) %BIGMOD

def nPr(fact,invFact,n,r):
    return(fact[n] * invFact[r])%BIGMOD

def fact(num):
    ans = 1
    for i in range(1,num+1):
        ans = ans*i%BIGMOD
    return ans

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

S = list(set(D))
S.sort()
if S[0]==0:
    S.pop(0)
ans = 1
before = 0
before_i = 0
for i in S:
    if i == 1:
        before = D.count(i)
        before_i = i
        continue
    ans = ans*modPow(before,D.count(i))%BIGMOD
    before = D.count(i)
    if i - before_i!=1:
        ans = 0
    before_i = i
if D[0] >0:
    print(0)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

l = []

for i in range(N):
  l.append(D.count(i))

ans = 1  

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

if D[0] != 0:
  print(0)
else:
  print(ans%998244353)

Submission status: Time Limit Exceeded

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

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

if d[0]!=0:
  print(0)
  exit()
  
kyori=[] #1からmaxdまでの距離について、それぞれ何個のdが該当するかメモした配列
maxd=max(d)

for i in range(0,maxd+1):
  kyori.append(d.count(i))

#1個目以外で距離0のやつある場合は停止。
if kyori[0]!=1:
  print(0)
  exit()

ans=1
for i in range(1,maxd):
  temp=kyori[i]**kyori[i+1]
  ans*=temp%998244353
  ans=ans%998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power_mod(a, n, mod):
    a=a%mod
    if n==0:
        return 1
    elif n==1:
        return a
    elif n%2==0:
        return power_mod(a,n//2,mod)**2%mod
    else:
        return (power_mod(a,(n-1)//2,mod)**2%mod)*a%mod

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

if distances[0] != 0 or distances.count(0) >= 2:
    print(0)
else:
    maximum=max(distances)
    count_dist=[1]
    for i in range(maximum):
        count_dist.append(distances.count(i+1))
    if count_dist.count(0) >= 1:
        print(0)
    else:
        count=1
        for i in range(maximum):
            count = count*power_mod(count_dist[i],count_dist[i+1],998244353)%998244353
        print(count)

Submission status: Time Limit Exceeded

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

mod=998244353
if D[0]!=0:
  print(0)
else:
  ans=1
  for i in range(2,n):
    ans*=D.count(i-1)**D.count(i)
    if ans==0:
      print(ans)
      exit()
  print(ans%mod)

Submission status: Time Limit Exceeded

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

max_vertex = max(l)
ll = []

for i in range(1, max_vertex+1):
    if l.count(i) == 0:
        print(0)
        exit()
    ll.append(l.count(i))

count = 1
for i in range(1, max_vertex):
    tmp = ll[i-1]
    count *= pow(tmp, ll[i])
print(count%998244353)

Submission status: Time Limit Exceeded

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

num_at_dist = [1] + [0] * (N-1) + [0] # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D.sort()
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

num_at_dist = [1] + [0] * (N-1) + [0] # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D.sort()
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
D = list(map(int, input().split()))
c = [0]*(N + 1)
a = 0
ans = 1
mod = 998244353
 
for i, d in enumerate(D):
    if (i == 0) & (d != 0):
        print(0)
        a = 1
        break
    if (i != 0) & (d == 0):
        print(0)
        a = 1
        break
    c[d] += 1


if a == 0:
    for o in range(1, N):
        ans *= c[o]**c[o + 1]

    
    print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

#1番目以外で1との距離が0はありえんのでそれは消す
for i in range(n):
  if i!=0:
    if d[i]==0:
      print(0)
      exit()

kyori=[] #1からmaxdまでの距離について、それぞれ何個のdが該当するかメモした配列
maxd=max(d)

for i in range(1,maxd+1):
  kyori.append(d.count(i))

#print(kyori)

ans=1
for i in range(maxd-1):
  temp=kyori[i]**kyori[i+1]
  ans*=temp%998244353
  ans=ans%998244353

print(ans)

Submission status: Time Limit Exceeded

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

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

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

    tmp = 1
    ans = 1
    for i in range(1, max(d)+1):
        count = d.count(i)
        if count == 0:
            print('0')
            exit() 
        ans *= tmp ** count
        ans %= mod
        tmp = count

    print(ans)

Submission status: Time Limit Exceeded

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

mod=998244353
if D[0]!=0:
  print(0)
else:
  ans=1
  cnt=[0]*n
  for i in range(1,n):
    cnt[i]=D.count(i)
  for i in range(2,n):
    if cnt[i]>0:
      ans*=cnt[i-1]**cnt[i]
      
  print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int, input().split()))
li = sorted(li)
count = 1
if not (1 in li and 0 in li):
    count = 0
else:
    for i in range(2,max(li) + 1):
        a = li.count(i-1)
        b = li.count(i)
        count *= a ** b
print(count % 998244353)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
D_list = list(map(int, input().split()))
mod = 998244353
ans = 1
count_dir = collections.Counter(D_list)
if max(D_list) >= N:
    ans = 0
else:
    for i in range(max(D_list) + 1):
        if i not in D_list:
            ans = 0
            break
        if i >= 2:
            ans *= count_dir[i-1]**count_dir[i]

if D_list[0] != 0 or count_dir[0] >= 2:
    ans = 0

print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if (D[0] != 0) or (x[0] != 1):
  ans = 0
  print(ans % MOD)
  quit()
  
fi = 0
for i in range(N-1):
  ans = ans * (x[i] ** x[i + 1])
  if x[i] == 0:
    fi = 1
  if (fi == 1) and (x[i] != 0):
    ans = 0
    print(ans)
    quit()
    
if (fi == 1) and (x[N-1] != 0):
  ans = 0
print(ans % MOD)

Submission status: Time Limit Exceeded

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


if D[0] != 0:
    ans = 0
else:
    ans = 1
    cnt = 1
    for i in range(max(D)+1):
        ans = ans * (cnt ** D.count(i)) % 998244353
        cnt = D.count(i)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 1
cnt = 1
for i in range(max(D)+1):
    if D[0] != 0 or i not in D:
        ans = 0
        break
    else:
        ans = ans * (cnt ** D.count(i)) % 998244353
        cnt = D.count(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353

N=int(input())
L=[0 for i in range(N)]
D=list(map(int,input().split()))
#print(D)
for i in range(N):
    L[D[i]]+=1
#print(L)

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

ans=1
cnt=1
for i in range(1,N):
    ans*=L[i-1]
    ans**=L[i]
    ans%mod
    cnt+=L[i]
    #print(ans,cnt)
    if cnt==N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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()
ans=1
tmp=1
for i in range(1,max(l)+1):
    c=l.count(i)
    if c==0:
        print(0)
        exit()
    ans*=modpow(tmp,c,MOD)
    ans%=MOD
    tmp=c
print(ans)

Submission status: Time Limit Exceeded

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

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

ans=1
from collections import Counter
c=Counter(d)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
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)
def modinv(a,MOD):
    return modpow(a,MOD-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()
ans=1
tmp=1
for i in range(1,max(l)+1):
    c=l.count(i)
    ans*=modpow(tmp,c,MOD)
    ans%=MOD
    tmp=c
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
if A[0] != 0:
  print(0)
  exit()
AC = list(Counter(A).items())
AC.sort()
MOD = 998244353
ans = 1
last_v = 1
last_k = -1
for k, v in AC:
  if k == 0:
    if v != 1:
      print(0)
      exit()
    last_k = 0
    continue
  if k != last_k+1:
    print(0)
    exit()
  ans = ans*pow(last_v, v, MOD)%MOD
  last_v = v
  last_k = k
print(ans)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n = k()
d = l()

count = Counter(d)
if d[0] == 0 and d.count(0) == 1:
    ans = 1
else:
    ans = 0

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

Submission status: Accepted

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

isOK=True
if D[0]!=0:
    isOK=False

for i in range(1,N):
    if D[i]==0:
        isOK=False
        break

cnt=[0]*(max(D)+1)
MOD=998244353
for i in range(N):
    cnt[D[i]]+=1

ans=1
for i in range(len(cnt)-1):
    
    for r in range(cnt[i+1]):
        ans=ans*cnt[i]%MOD
if isOK:
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
if a[0]==0 and a.count(0)==1:
  ans=1
else:
  ans=0
a=collections.Counter(a)
for i in range(max(a)):
  ans*=a[i]**a[i+1]
  ans%=998244353
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
d = list(map(int, input().split()))
dist = [0]*n

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

ans = 1

if d[0]!=0:
    ans = 0
elif dist[0] != 1:
    ans = 0
else:
    for i in range(2,n):
        if dist[i-1]==0 and dist[i]!=0:
            ans = 0
            break
        elif dist[i] == 0:
            continue
        else:
            for j in range(dist[i]):
                ans *= dist[i-1]
            if ans > 998244353:
                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()
d.sort()
mod = 998244353
s = [0 for i in range(max(d)+1)]

for i in range(n):
  s[d[i]] += 1
ans = 1
for i in range(len(s)):
  if s[i] == 0:
    print (0)
    exit()
  if i == 0:
    if s[i] > 1:
      print (0)
      exit()
    continue
  ans *= pow(s[i-1],(s[i]),mod)
  ans %= mod
print (ans%mod)

Submission status: Accepted

Solution code:
N,D=open(0)
*D,=map(int,D.split())
c=[0]*-~max(D)
for i in D:c[i]+=1
a=D[0]<1==c[0]
for i,j in zip(c,c[1:]):a*=i**j
print(a%998244353)

Submission status: Accepted

Solution code:
N,*D=map(int,open(0).read().split())
c=[0]*N
for i in D:c[i]+=1
m=max(D)
if D[0]>0 or c[0]>1:print(0);exit()
a=1
for i in range(m):a*=c[i]**c[i+1]
print(a%998244353)

Submission status: Accepted

Solution code:
n=int(input())
mod=998244353
A=list(map(int,input().split()))
import sys
# mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  #frac(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

C=Counter(A)
if A[0]!=0 or A.count(0)>1:
    print(0);exit()
Q=[C[i] for i in range(max(A)+1)]
#print(Q)
ans=1
for i  in range(len(Q)-1):
    ans*= pow(Q[i],Q[i+1],mod)
    ans%=mod

print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():




    n = I()
    d = LI()
    mod = 998244353
    
    dcnt = [0]*(max(d)+1)
    

    for x in d:
        dcnt[x] += 1

    nexist = d[0]!=0 or 0 in dcnt or 0 in d[1:]
    if nexist:
        print(0)
        exit(0)

    
    ans = 1

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

    print(ans)
                    


main()

Submission status: Accepted

Solution code:
from collections import Counter
 
 
def solve(n, ddd):
    if ddd[0] != 0:
        return 0
    cnt = Counter(ddd)
    if cnt[0] != 1:
        return 0
    max_c = max(cnt)
    for i in range(max_c + 1):
        if i not in cnt:
            return 0
 
    MOD = 998244353
    ans = 1
    for i in range(max_c):
        prev = cnt[i]
        curr = cnt[i + 1]
        ans = ans * pow(prev, curr, MOD) % MOD
    return ans
 
 
n = int(input())
ddd = list(map(int, input().split()))
 
print(solve(n, ddd))

Submission status: Accepted

Solution code:
from collections import Counter

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

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

C = sorted(Counter(D).most_common(), key=lambda x: x[0])

if C[0][1] > 1:
    print(0)
    exit()

ans = 1
for i in range(1, len(C)):
    if C[i][0] - C[i-1][0] > 1:
        print(0)
        exit()
    ans *= C[i - 1][1] ** C[i][1]

print(ans % MOD)

Submission status: Accepted

Solution code:

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

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

    CNT = [0] * N
    for i in D:
        CNT[i] += 1

    if CNT[0] > 1:
        print(0)
        return

    ans = 1
    for i in range(1, N):
        ans *= pow(CNT[i - 1], CNT[i], MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

from collections import Counter
def resolve():
    MOD = 998244353
    N = int(input())
    D = list(map(int, input().split()))

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

    CNT = Counter(D)
    if CNT[0] > 1:  # 距離0は1個
        print(0)
        return

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

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

mod = 998244353

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

d = defaultdict(int)

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

MOD=998244353
N,D = ilint()
if D[0]!=0:
    print(0)
    exit()
C = [0]*N
C[0]=1
for d in D[1:]:
    if d==0:
        print(0)
        exit()
    C[d] += 1
ans=1
for i in range(1,max(D)+1):
    ans *= powmod(C[i-1],C[i],MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#B
import sys
from collections import Counter
n=int(input())
d=list(map(int,input().split()))
e=Counter(d)
mod=998244353
if d[0]!=0 or e[0]!=1:
    print(0)
    sys.exit()
ans=1
for i in range(2,n):
    ans*=pow(e[i-1],e[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)
else:
    tmp = [0 for _ in range(10 ** 5)]
    for i in range(N):
        tmp[D[i]] += 1

    if tmp[0] != 1:
        print(0)
    else:
        ans = 1
        flag = False
        flag2 = False
        for i in range(1, 10 ** 5 - 1):

            if flag2 and tmp[i+1] != 0:
                ans = 0
                break

            if tmp[i+1] == 0:
                flag2 = True

            ans = (ans * (tmp[i] ** tmp[i+1])) % 998244353

        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
D=list(map(int,input().split()))
mod=998244353
if D[0] != 0:
    print(0)
else:
    ans=1
    del D[0]
    if 0 in D:
        print(0)
    else:
        numbers=Counter(D)
        for n in range(2,max(numbers.keys())+1):
            if numbers[n]==None:
                ans=0
                break
            ans*=numbers[n-1]**numbers[n]
        print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
r=1 if d[0]==0 else 0
d=d[1:]
d.sort()
c=1
nc=0
j=1
mod=998244353
for i in d:
  if i<j:
    r=0
  elif i==j:
    nc+=1
    r=(r*c)%mod
  elif i==j+1:
    j=i
    c=nc
    nc=1
    r=(r*c)%mod
  else:
    r=0
print(r)

Submission status: Accepted

Solution code:
from collections import Counter

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

if d[0]:
  print(0)
  exit()
  
dmax = max(d)
if sorted(set(d)) != list(range(dmax+1)):
  print(0)
  exit()

c = Counter(d)

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

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

Submission status: Accepted

Solution code:
import collections
n = int(input())
d = list(map(int, input().split()))
mod = 998244353
f = collections.Counter(d)
# print(f)
if d[0] != 0 or f[0] != 1:  # 0は一個だけ
    print(0)
    exit()
ans = 1
box = 1  # 値自体の個数を保存
maxd = max(d)

for i in range(maxd+1):
    ans = ans*box**f[i]
    ans %= mod
    box = f[i]
print(ans)