Submission #11379810

---

Source Code Expand

import sequtils,strutils,math,algorithm
const M=10^9+7
proc`%`(a,b:int):int=
  if a<0:(a+(-a div b+1)*b)mod b
  else:a mod b
proc pow(a,b,p:int):int=
  if b==0:1
  elif b==1:a
  elif b%2>0:pow(a,b-1,p)*a%p
  else:pow(a,b div 2,p)^2%p
proc facTable(N:int):(seq[int],seq[int])=
  var fac=newSeq[int](N+1)
  fac[0]=1
  for i in 1..N:fac[i]=fac[i-1]*i%M
  var inv=newSeq[int](N+1)
  inv[N]=pow(fac[N],M-2,M)
  for i in N.countdown 1:inv[i-1]=inv[i]*i%M
  (fac,inv)
const
  table=facTable(1000)
  fac=table[0]
  inv=table[1]
let n=stdin.readLine.parseInt
var
  e=newSeq[seq[int]] n
  o=newSeq[int]()
  s= @[0]
  f=newSeq[bool] n
  dp1,dp2,sz1,sz2=newSeq[int] n
  c=newSeq[(seq[int],seq[int])] n
e.fill newSeq[int]()
for _ in 2..n:
  var a,b=0
  (a,b)=stdin.readLine.split.map parseInt
  e[a-1].add b-1
  e[b-1].add a-1
while s.len>0:
  let v=s.pop
  f[v]=true
  o.add v
  var l=newSeq[int]()
  for w in e[v]:
    if f[w]:continue
    l.add w
    s.add w
  e[v]=l
for v in o.reversed:
  var c1,c2= @[1]
  sz1[v]=1
  for i,w in e[v]:
    c1.add c1[i]*dp1[w]%M*inv[sz1[w]]%M
    sz1[v]+=sz1[w]
  for i,w in e[v].reversed:
    c2.add c2[i]*dp1[w]%M*inv[sz1[w]]%M
  c2.reverse
  dp1[v]=c2[0]*fac[sz1[v]-1]%M
  c[v]=(c1,c2)
dp2[0]=1
sz2[0]=1
for v in o:
  let
    c1=c[v][0]
    c2=c[v][1]
  for i,w in e[v]:
    sz2[w]=sz2[v]+sz1[v]-sz1[w]
    dp2[w]=dp2[v]*inv[sz2[v]-1]%M*c1[i]%M*c2[i+1]%M*fac[sz2[w]-2]%M
var a=0
for i in 0..<n:
  a=(a+dp1[i]*dp2[i]%M*inv[sz1[i]-1]%M*inv[sz2[i]-1]%M*fac[sz1[i]+sz2[i]-2]%M)%M
echo a*pow(2,M-2,M)%M

Submission Info

Compile Error

Hint: system [Processing]
Hint: Main [Processing]
Hint: sequtils [Processing]
Hint: strutils [Processing]
Hint: parseutils [Processing]
Hint: math [Processing]
Hint: times [Processing]
Hint: algorithm [Processing]
Main.nim(41, 7) Warning: 'l' should not be used as an identifier; may look like '1' (one) [SmallLshouldNotBeUsed]
Main.nim(44, 5) Warning: 'l' should not be used as an identifier; may look like '1' (one) [SmallLshouldNotBeUsed]
Main.nim(46, 8) Warning: 'l' should not be used as an identifier; may look like '1' (one) [SmallLshouldNotBeUsed]
Hint:  [Link]
Hint: operation successful (15241 lines compiled; 2.255 sec total; 18.184MB; Release Build) [SuccessX]

Judge Result