Submission #26559753

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N = gets.to_i
M = 10**9+7
E = Array.new(N){{}}
$<.each{|ln|
  a,b = ln.split.map{_1.to_i-1}
  E[a][b] = nil
  E[b][a] = nil
}
D = E.map(&:size)
C = lambda{|max|
  num,dnm = [1,1],[1,1]
  2.upto(max){|n|
    num << num[-1]*n%M
    dnm << M - dnm[M%n]*(M/n)%M # 謎
  }
  1.upto(dnm.size-1){|n|
    dnm[n] = dnm[n-1]*dnm[n]%M # 謎
  }
  next lambda{|n,r|
    num[n]*dnm[r]*dnm[n-r]%M
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N = gets.to_i
M = 10**9+7
E = Array.new(N){{}}
$<.each{|ln|
	a,b = ln.split.map{_1.to_i-1}
	E[a][b] = nil
	E[b][a] = nil
}
D = E.map(&:size)
C = lambda{|max|
	num,dnm = [1,1],[1,1]
	2.upto(max){|n|
		num << num[-1]*n%M
		dnm << M - dnm[M%n]*(M/n)%M # 謎
	}
	1.upto(dnm.size-1){|n|
		dnm[n] = dnm[n-1]*dnm[n]%M # 謎
	}
	next lambda{|n,r|
		num[n]*dnm[r]*dnm[n-r]%M
	}
}.call N

P = [nil]*N
Q = N.times.select{ D[_1]<2 }
while a = Q.pop
	pr,nd = 1,0
	E[a].each{|b,(pr2,nd2)|
		if pr2
			pr = pr*pr2*C[nd+nd2,nd]%M
			nd += nd2
		else
			P[a] = b
		end
	}
	break unless P[a]
	E[P[a]][a] = [pr,nd+1]
	Q << P[a] if 1 == D[P[a]] -= 1
end

Q << a
while a = Q.pop
	pr,nd = 1,0
	E[a].each{|b,(pr2,nd2)|
		pr = pr*pr2*C[nd+nd2,nd]%M
		nd += nd2
	}
	E[a].each{|b,(pr2,nd2)|
		next if b==P[a]
		E[b][a] = [pr*pr2.pow(M-2,M)*C[nd,nd2].pow(M-2,M)%M,nd-nd2+1]
		Q << b
	}
end

puts E.map{|bs|
	bs.values.inject([1,0]){|(pr,nd),(pr2,nd2)|
		next pr*pr2*C[nd+nd2,nd]%M,nd+nd2
	}[0]
}

Submission Info

Judge Result