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:
N = int(input())
D = list(map(int, input().split()))

if D[0] != 0:
    print(0)
else:
    D.sort()

    D_num = []
    count = 1
    for i in range(N):
        if i == N-1 or D[i] != D[i+1]:
            D_num.append([D[i],count])
            count = 1
        else:
            count += 1

    D_max = D[N-1]

    if D_num[0][1] != 1:
        print(0)
    elif len(D_num) != D_max+1:
        print(0)
    else:
        result = 1
        for i in range(1,D_max+1):
            result = result * D_num[i-1][1] ** D_num[i][1]
            result = result % 998244353

        print(result)

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  x = c[i]
  while x:
    r = r * pow(p, x, M) % M
    i += 1; n -= x; p = x; x = c[i]
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  x = c.get(i)
  while x:
    r = r * pow(p, x, M) % M
    i += 1; n -= x; p = x; x = c.get(i)
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = i = 1
  x = c.get(i)
  while x:
    n -= x
    r = r * pow(p, x, M) % M
    i += 1; p = x; x = c.get(i)
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = p = 1
  try:
    for i in range(1, n + 1):
      x = c.get(i)
      r = r * pow(p, x, M) % M
      p = x; n -= p
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = x = 1
  try:
    for i in range(1, n):
      p = x; x = c.get(i); n -= x
      r = r * pow(p, x, M) % M
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = x = 1
  try:
    for i in range(1, n):
      p = x; x = c.get(i)
      r = r * pow(p, x, M) % M
      n -= x
  except:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = x = 1
  try:
    for i in range(1, n):
      p = x; x = c.get(i); n -= x
      r = r * pow(p, x, M) % M
  except TypeError:
    pass
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
from collections import Counter
 
M = 998244353
n = int(input())
a = map(int, input().split())
x, c = next(a), Counter(a)
r = 0
if x == c[0] == 0:
  r = x = 1
  for i in range(1, n):
    p = x; x = c.get(i)
    if x is None:
      break
    r = r * pow(p, x, M) % M
    n -= x
print((r, 0)[n > 1])

Submission status: Accepted

Solution code:
import sys
import collections

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

if D[0] != 0:
    print(0)
    sys.exit()
DD = collections.Counter(D)
max_key = max(DD.keys())
result = 1
last_v = 0
for k in range(max_key + 1):
    if not k in DD:
        print(0)
        sys.exit()
    v = DD[k]
    if k == 0:
        if v > 1:
            print(0)
            sys.exit()
        last_v = v
        continue
    result *= last_v ** v
    last_v = v
print(result % 998244353)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
li = list(map(int, input().split()))
c = Counter(li)
a = 1
M = 998244353
if li[0] != 0 or c[0] != 1:
  print(0)
else:
  for i in range(1, max(li)):
    a *= (c[i]**c[i+1])
  print(a%M)

Submission status: Accepted

Solution code:
N=int(input())
D=list(map(int,input().split()))
from collections import Counter
import sys
d=Counter(D)
M=1
if D[0]!=0 or d[0]!=1:
    print(0)
    sys.exit()
for i in range(max(D)-1):
    M*=d[i+1]**d[i+2]
print(M%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

if D[0] != 0 or D.count(0) > 1:
    print(0)
else:
    c = Counter(D)
    for key in c:
        if key == 0:
            continue
        elif key-1 in c == False:
            ans = 0
            break
        else:
            ans = ans * c[key-1] ** c[key]
    print(ans % 998244353)

Submission status: Accepted

Solution code:
N =int(input())
D = [int(x) for x in input().split()]
cnt = [0]*(N)
if D[0]!=0:
  print(0)
  exit()
for i in range(N):
  cnt[D[i]]+=1
ans = 1
if cnt[0]!=1:
  print(0)
  exit()
a = 0
b = 0
for i in range(1,N-1):
  if cnt[i]==0 and a==0:
    a=i
    b+=1
  if a!=0 and cnt[i]!=0:
    print(0)
    exit()
  elif a!=0 and cnt[i]==0:
    b+=1
  ans*=cnt[i-1]**cnt[i]
  ans%=998244353
#print(cnt,a,b)
if N-a==b or a==b==0:
  print(ans)
else:
  print(0)

Submission status: Accepted

Solution code:
N = int(input())
D = [int(d) for d in input().split()]
maxD = max(D)
length = [0 for _ in range(maxD+1)]
mod = 998244353
for d in D:
    length[d] += 1
if D[0] != 0 or length[0] > 1:
    print(0)
else:
    ans = 1
    for i in range(1, maxD + 1):
        if length[i] == 0:
            print(0)
            break
        else:
            ans *= (length[i-1] ** length[i]) % mod
            ans %= mod
    else:
        print(ans)

Submission status: Accepted

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


def main():
    from collections import Counter

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

    # KeyInsight
    # 条件を満たす個数：距離Diの頂点に対して親の個数の数だけ辺が張れるか，と言い換え

    # 気がつけた点
    # D1は0，それ以外は1l以上であるかどうかで場合分け
    # サンプルから組み合わせを愚直に数えた

    # 気がつけなかった点
    # 各距離における組み合わせを効率的に求める方法．重複組み合わせを数えようとしていた
    if d[0] == 1 or (0 in d[1:]):
        print(0)
        exit()

    ans = 1
    mod = 998244353

    for i in c.keys():
        if i >= 1:
            ans *= c[i - 1] ** c[i]
            ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import Counter


def main():
    n = int(input().strip())
    d = list(map(int, input().strip().split()))
    if d[0] != 0:
        print(0)
        return
    e = sorted(list(set(d)))
    for i, v in enumerate(e):
        if i != v:
            print(0)
            return
    v = dict(Counter(d))
    if v[0] != 1:
        print(0)
        return
    i = 0
    ans = 1
    while True:
        if i in v:
            if i == 0:
                i += 1
                continue
            ans *= v[i-1] ** v[i]
            ans %= 998244353
        else:
            break
        i += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, D):
    if D[0] != 0:
        return 0
    C = Counter(D)
    if C[0] != 1:
        return 0
    ans = 1
    M = Mod(998244353)
    for i in range(max(D)):
        ans = M.mul(ans, M.pow(C[i], C[i+1]))
    return ans


def main():
    N = read_int()
    D = read_int_n()
    print(slv(N, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
  N = int(input())
  vD = list(map(int, input().split()))
  MOD = 998244353

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

  vD.sort()
  if vD[1]==0:
    print(0)
    return

  res = 1
  p = -1
  pcnt = 1
  ccnt = 1
  for d in vD:
    if d==p+1:
      pcnt = ccnt
      ccnt = 1
    elif d==p:
      ccnt += 1
    else: # d>=p+2
      print(0)
      return

    res *= pcnt
    res %= MOD
    p = d

  print(res)

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 or min(d[1:]) == 0:
    print(0)
else:
    c = Counter(d)
    ans = 1
    for i in range(1, max(d)+1):
        ans *= c[i-1] ** c[i]
        ans = ans % mod
    print(ans)

Submission status: Accepted

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

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

c=Counter(d)
d_max=max(d)
ans=1
flag=True

if d[0]!=0:
    print(0)
elif d.count(0)>1:
    print(0)
else:
    for i in range(1, d_max+1):
        if c[i-1]==0:
            flag=False
        else:
            ans=ans*(c[i-1]**c[i])%998244353

    print(ans%998244353 if flag else 0)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n1 = int(input()) - 1
d = list(map(int, input().strip().split()))
mod = 998244353
if d[0] != 0 or 0 in d[1:]:
    print(0)
else:
    max_path = max(d)
    flag = True
    v = [0 for i in range(max_path)]
    for i in d[1:]:
        v[i-1] += 1

    if 0 in v:
        flag = False

    if flag:
        num = 1
        hh = 1

        def binpow(a, b):
            if b == 0:
                return 1
            elif a == 1:
                return 1
            elif b % 2 == 0:
                c = binpow(a, b // 2)
                return (c ** 2) % mod
            else:
                return (binpow(a, b - 1) * a) % mod


        for h in v:
            num *= binpow(hh, h)
            num = num % mod
            hh = h

        print(num)

    else:
        print(0)

Submission status: Accepted

Solution code:
CONST_DIVSOR = 998244353
N = int(input())
Ds = list(map(int, input().strip().split()))
counter = [0] * (max(Ds)+1)
for D in Ds:
    counter[D] += 1
ans = 1
if counter[0] != 1 or Ds[0] != 0:
    print(0)
else:
    for i in range(1,max(Ds)+1):
        ans *= (counter[i-1] ** counter[i])
        ans %= CONST_DIVSOR
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n1 = int(input()) - 1
d = list(map(int, input().strip().split()))
mod = 998244353
if d[0] != 0 or 0 in d[1:]:
    print(0)
else:
    max_path = max(d)
    flag = True
    v = [0 for i in range(max_path)]
    for i in d[1:]:
        v[i-1] += 1

    if 0 in v:
        flag = False

    if flag:
        num = 1
        hh = 1

        for h in v:
            num *= hh ** h
            num = num % mod
            hh = h

        print(num)

    else:
        print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, = map(int, sys.stdin.readline().rstrip().split(" "))
Ds = list(map(int, sys.stdin.readline().rstrip().split(" ")))
if Ds.pop(0) != 0:
    print(0)
else:
    Ds.sort()
    leaf_count = collections.defaultdict(int)
    leaf_count[0] = 1
    result = 1
    for D in Ds:
        if leaf_count[D - 1] == 0:
            result = 0
            break
        else:
            result *= leaf_count[D - 1]
            result %= 998244353
            leaf_count[D] += 1
    print(result)
exit(0)

Submission status: Accepted

Solution code:

import collections

n = int(input())

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

waru = 998244353

c = collections.Counter(d)

ans =1

cmax =max(c.keys())
if d[0] != 0:
    print(0)
else:
    for i in range(1,cmax+1):
        if d[i] == 0:
            ans = 0
            break
        ans *= c[i-1]** c[i]

    print(ans % waru)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 998244353
if a[0] != 0:
  print(0)
  exit()
cnt = {}
for e in a:
  cnt[e] = cnt.get(e, 0) + 1
if cnt[0] > 1:
  print(0)
  exit()
d, c = 0, cnt[0]
ans = 1
for k, v in sorted(list(cnt.items())):
  # print(k, v)
  if k == 0:
    continue
  if k > d + 1:
    print(0)
    exit()
  for i in range(v):
    ans = ans * c % mod
  d, c = k, v
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=list(map(int,input().split()))
q=[0]*(max(d)+1)
#from collections import Counter
#q=Counter(d)


for i in range(len(d)):
    q[d[i]]+=1
    
if q[0]!=1 or d[0]!=0:
    print(0)
    exit()

ans=1
for i in range(1,max(d)+1):
    ans*=q[i-1]**q[i]
    if ans == 0:
        break
print(ans%998244353)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    count = [0] * N
    for d in D:
        count[d] += 1
    
    if D[0] != 0 or count[0] >= 2:
        print(0)
        exit()

    ans = 1
    for i in range(N):
        if i > 0:
            ans *= (count[i-1] ** count[i]) % 998244353
            ans %= 998244353

    print(ans)

    

if __name__ == '__main__':
        main()

Submission status: Accepted

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

def main():
    _ = int(input())
    D = list(map(int, input().split()))
    Dnum = Counter(D)
    if D[0] != 0 or Dnum[0] != 1:
        print(0)
        exit()
    ans = 1
    for i in range(1, max(D)+1):
        ans *= Dnum[i] ** Dnum[i+1]
        if ans == 0:
            break
    print(ans%998244353)


if __name__ == '__main__': main()

Submission status: Accepted

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

from collections import Counter
q=Counter(d)

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

ans=1
for i in range(1,max(d)+1):
    ans*=q[i-1]**q[i]
    if ans == 0:
        break
print(ans%998244353)

Submission status: Accepted

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

# 例外対応
if q[0]!=1 or d[0]!=0:
  print(0)
  exit()

ans = 1
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)

Submission status: Accepted

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

f=True

if D[0]!=0:
	f=False
D.sort()

d={}
a=0
for i in range(N):
	if D[i] not in d:
		if D[i]==a:
			d[D[i]]=1
			a=D[i]+1
		else:
			f=False
			break
	else:
		d[D[i]] += 1

if not(f):
	print(0)
elif d[0]>1:
	print(0)
else:
	ans=1
	d = list(d.values())
	for i in range(1, len(d))[::-1]:
		ans *= (d[i-1]**d[i])%998244353
		ans %= 998244353
	print(ans)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(d)

ans = 1

if c[0] != 1 or d[0] !=0:
    ans = 0

for i in range(max(d) + 1):
    if i == 0:
        continue
    ans *= c[i-1] ** c[i]

print(ans%998244353)

Submission status: Accepted

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

Submission status: Accepted

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

if d[0] != 0 or min(d[1:]) == 0:
	print(0)
else:
	ans = 1
	c = Counter(d)
	for k, v in c.items():
		if k == 0:
			continue
		ans *= pow(c[k-1], v, MOD)
		ans %= MOD
	print(ans)

Submission status: Accepted

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

from collections import Counter
q=Counter(d)

ans = 1
if q[0]!=1 or d[0]!=0:
    print(0)
    exit()
d.sort()
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    D=list(map(int,input().split()))
    c=collections.Counter(D)
    k=list(c.keys())
    v=list(c.values())
    ans=1 if c[0] == 1 and D[0] == 0 else 0
    for i in range(max(k)):
        ans*=c[i]**c[i+1]
        ans%=998244353
        if ans == 0:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
l = list(map(int, input().split()))
m = [0]*(max(l)+1)

for x in l:
    m[x] += 1
if l[0] != 0 or not all(l[1:]) :
    print(0)
    exit()
t = 1
r = 1
for x in m:
    t = t * pow(r,x,mod) % mod
    r = x

print(t)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    _ = int(args[0])
    D = list(map(int, args[1].split()))

    max_d = max(D)

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 0
    if D[0] == 0 and nodes.count(0) == 0 and nodes[0] == 1:
        ret = 1
        for i in range(2, max_d+1):
            ret *= pow(nodes[i-1], nodes[i], 998244353)

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
n = int(input())
d = (int(s) for s in input().split())
if next(d) != 0:
    print(0)
    quit(0)
c = Counter(d)
if c[0] != 0:
    print(0)
    quit(0)
print(reduce(lambda x, y: x * y, (c[k - 1] ** x if k > 1 else 1 for k, x in c.items()), 1) % 998244353)

Submission status: Accepted

Solution code:
import numpy as np
import collections
input1 = list(map(int,input().split()))
input2 = list(map(int,input().split()))

N = input1[0]
D = input2

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

counter = collections.Counter(D)

ans = 1

D.sort()
D_numpy = np.array(D)
if (np.diff(D_numpy)<=1).prod():
  if counter[0] != 1:
    ans = 0
  else:
    for i in range(len(counter)):
      ans *= counter[i]**counter[i+1]
      if ans >= 998244353:
        ans = ans%998244353

else:
  ans = 0



print(ans)

Submission status: Accepted

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


count = [0] * N
for d in D:
    count[d] += 1

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

print(ans)

Submission status: Accepted

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

count = [0] * N
for d in D:
    count[d] += 1

if (D[0] != 0 or count[0] >= 2):
    print(0)
    exit()
ans = 1
for i in range(N):
    if (i > 0):
        ans *= (count[i - 1] ** count[i]) % MOD
        ans %= MOD

print(ans)

Submission status: Accepted

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

# print(ans)


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

# 厳密にはmax(D)+1の長さがあれば正常系は通るが、余分に取っておく
count = [0] * N
for d in D:
    count[d] += 1

# def calc():
if D[0] != 0 or count[0] >= 2:
    print(0)
    exit()
ret = 1
for i in range(N):
    if i > 0:
        ret *= (count[i-1] ** count[i]) % MOD
        ret %= MOD
print(ret)

Submission status: Accepted

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

# print(ans)


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

# 厳密にはmax(D)+1の長さがあれば正常系は通るが、余分に取っておく
count = [0] * N
for d in D:
    count[d] += 1

def calc():
    if D[0] != 0 or count[0] >= 2:
        return 0
    ret = 1
    for i in range(N):
        if i > 0:
            ret *= (count[i-1] ** count[i]) % MOD
            ret %= MOD
    return ret


print(calc())

Submission status: Accepted

Solution code:
import numpy as np
NUMBER = 998244353
 
N, *D = map(int, open(0).read().split())
bincnt = np.bincount(D)
if D[0] != 0:
    print('0')
elif (bincnt==0).sum() > 0:
    print('0')
elif bincnt[0]!=1:
    print('0')
else:
    val = 1
    for i in range(2, bincnt.shape[0]):
        for _ in range(bincnt[i]):
            val = (val*bincnt[i-1]%NUMBER)
    print(val)

Submission status: Accepted

Solution code:
import numpy as np
NUMBER = 998244353
 
N = int(input())
D = list(map(int, input().split()))
bincnt = np.bincount(D)
if D[0] != 0:
    print('0')
elif (bincnt==0).sum() > 0:
    print('0')
elif bincnt[0]!=1:
    print('0')
else:
    val = 1
    for i in range(2, bincnt.shape[0]):
        for _ in range(bincnt[i]):
            val = (val*bincnt[i-1]%NUMBER)
    print(val)

Submission status: Accepted

Solution code:
# 再帰関数の最大再帰回数を変更
import sys
sys.setrecursionlimit(1000000)

# 再帰関数で作る木の個数を返す
def dfs(now, end, summary):
    # 終了条件
    if now == end:
        return summary
    # 1つ前の頂点時点で作ることのできる木の個数 *（１つ前の深さの頂点の数 ^ 現在の深さの頂点の数）で再帰関数
    else:
        return dfs(now + 1, end, summary * (deep[now - 1] ** deep[now]))

# 最後に割る数の定数
JOSU = 998244353

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

# 深さをメモするため、Dの最大値 + 1の数の配列を用意
# 例：深さの最大が2なら、0, 1, 2の3つが必要
deep = [0] * (max(D) + 1)

# 各深さの頂点の数を記録
for i in range(N):

    # 頂点1が深さ0以外なら制約違反
    if i == 0 and D[i] != 0:
        print(0)
        exit()
    # 頂点1以外が深さ0なら制約違反
    elif i > 0 and D[i] == 0:
        print(0)
        exit()

    deep[D[i]] += 1

# 再帰関数で計算
print(dfs(1, len(deep), 1) % JOSU)

Submission status: Accepted

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
 
import collections
 
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
c = collections.Counter(D)
if c[0] > 1:
  ans=0
for i in S:
    if i == 1:
        before = c[i]
        before_i = i
        continue
    ans = ans*modPow(before,c[i])%BIGMOD
    before = c[i]
    if i - before_i!=1:
        ans = 0
    before_i = i
if D[0] >0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
d=[int(i) for i in input().split()]
mod = 998244353

if d[0]!=0:
    print(0)    
    exit()
for i in d[1:]:
    if i==0:
        print(0)
        exit()
    
    
d=sorted(d)
ans = 1
    
dic = defaultdict(int)
dic[0] = 1
for i in d[1:]:
    ans *= dic[i-1]
    ans = ans % mod
    dic[i] += 1
print(ans)

Submission status: Accepted

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

# 厳密にはmax(D)+1の長さがあれば正常系は通るが、余分に取っておく
count = [0] * N
for d in D:
    count[d] += 1

def calc():
    if D[0] != 0 or count[0] >= 2:
        return 0
    ret = 1
    for i in range(N):
        if i > 0:
            ret *= (count[i-1] ** count[i]) % MOD
            ret %= MOD
    return ret

print(calc())

Submission status: Accepted

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

# 厳密にはmax(D)+1の長さがあれば正常系は通るが、余分に取っておく
count = [0] * N
for d in D:
    count[d] += 1

def calc():
    if D[0] != 0:
        return 0
    ret = 1
    for i in range(N):
        if i == 0:
            if count[i] >= 2:
                return 0
        else:
            ret *= (count[i-1] ** count[i]) % MOD
            ret %= MOD
    return ret

print(calc())

Submission status: Accepted

Solution code:
import collections
 
N=int(input())
D=list(map(int,input().split()))
 
c=collections.Counter(D)
 
max_D=max(D)
ans=1
previous_leaf=1
 
if D[0]!=0:
    ans=0
elif c[0]!=1:
    ans=0
else:
    for i in range(1,max_D+1):
        ans*=(previous_leaf**c[i])
        ans%=998244353
        previous_leaf=c[i]
 
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=998244353
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    D=list(map(int,input().split()))
    M=max(D)

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

    C=[0]*(M+1)
    for d in D:
        C[d]+=1

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

    if(any(C[i]==0 for i in range(M+1))):
        print(0)
        return

    ans=1
    for i in range(1,M+1):
        ans*=pow(C[i-1],C[i],MOD)
        ans%=MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
n,*d=map(int,open(0).read().split())
e=[0]*n
for i in d:e[i]+=1
a=d[0]<1==e[0]
for x,y in zip(e,e[1:]):a=a*x**y%998244353
print(a)

Submission status: Accepted

Solution code:
_,d=open(0)
*d,=map(int,d.split())
e=[0]*10**5
for i in d:e[i]+=1
a=d[0]<1==e[0]
for x,y in zip(e,e[1:]):a=a*x**y%998244353
print(a)

Submission status: Accepted

Solution code:
_,d=open(0)
*d,=map(int,d.split())
e=[0]*-~max(d)
for i in d:e[i]+=1
a=d[0]<1==e[0]
for x,y in zip(e,e[1:]):a*=x**y
print(a%998244353)

Submission status: Accepted

Solution code:
import collections

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

c=collections.Counter(D)

max_D=max(D)
ans=1
previous_leaf=1

if D[0]!=0:
    ans=0
elif c[0]!=1:
    ans=0
else:
    for i in range(1,max_D+1):
        ans*=(previous_leaf**c[i])
        ans%=998244353
        previous_leaf=c[i]

print(ans)

Submission status: Accepted

Solution code:
mod=998244353
def modpow(a,p):
    res=1
    for i in range(p):
        res*=a
        res%=mod
    return res

n=int(input())
d=input().split(" ")
a={}
for i in range(0,n):
    a.setdefault(i,0)
for i in d:
    a[int(i)]+=1
ans=1
if d[0]!='0' or a[0]!=1:
    ans=0
else:
    for i in range(n-1):
        ans*=modpow(a[i],a[i+1])
        ans%=mod

print(ans)