AtCoder ARC #044 B - 最短路問題

arc044-b.rb

R = 10**9+7
N = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
if a[0] != 0
  puts 0
  exit
end
amax = a.max
h = Array.new(amax+1, 0)
a.each do |i|
  h[i] += 1
end
if h[0] != 1
  puts 0
  exit
end
h.each do |i|
  if i == 0
    puts 0
    exit
  end
end

@pow2 = Array.new(N+1, 0)
@pow2[0] = 1
(N).times do |i|
  @pow2[i+1] = @pow2[i] * 2
  @pow2[i+1] %= R
end

def pow2mod(n)
  ret = 1
  if n > N
    while n > N
      ret *= @pow2[N]
      ret %= R
      n -= N
    end
  end
  ret *= @pow2[n]
  ret %= R
  return ret
end

ans = 1
b = 1
h[1..amax].each do |i|
  ans *= pow2mod(i * (i - 1) / 2)
  ans %= R
  ans *= (((@pow2[b] - 1) % R) ** i)
  ans %= R
  b = i
end
puts ans