Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、12問目を解説していきたいと思います。
問題名 【B – Counting of Trees】
入力
N：数列の長さ
D[i] : i番目の数字
考察
木構造について理解する
- 深さ0の葉は根
- 深さ1の葉は深さ0の葉(=根)とつながっている
- 深さ2の葉は深さ1の葉のどれか一つとつながっていて、深さ1の葉は深さ0の葉(=根)とつながっている
- 深さ3の葉は深さ2の葉のどれか一つとつながっていて、深さ2の葉は深さ1の葉のどれか一つとつながっていて、深さ1の葉は深さ0の葉(=根)とつながっている
と考えることができます。
つまり、木構造において、深さiの葉が根までの行き方は
深さiの葉は、i-1番目の枝までの行き方 × i-1番目の枝が根までの行き方と考えられます。
コード
from collections import Counter
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = II()
D = LI()
# D.sort()
c = Counter(D)
if c[0]!=1 or D[0]!=0:
print(0)
exit()
ans = 1
mod = 998244353
for i in c.keys():
if i>=1:
ans*=(pow(c[i-1],c[i]))
ans%=mod
print(ans%mod)まとめ
意外とむずかった・・・
前の問題 011【D – Disjoint Set of Common Divisors】
次の問題 013【D – Lucky PIN】
コメント