Submission #2632348


Source Code Expand

Copy
# coding: utf-8
MOD = 1_000_000_007
 
class Combination
  def initialize
    @fact = (1..10**5+1).to_a
    @fact.each_with_index do |e, idx|
      @fact[idx] = @fact[idx] * @fact[idx-1] % MOD if idx > 0
    end
  end
 
  def choose(n, r)
    return 0 if not (0 <= r and r <= n)
    return 1 if r == 0 or r == n
    fact(n) * inverse( fact(r) * fact(n-r) )
  end
 
  def fact(n)
    @fact[n-1]
  end
 
  def inverse(x)
    pow(x, MOD-2)
  end
 
  def pow(x, n)
    ans = 1
    while n > 0
      ans = ans * x % MOD if n.odd?
      x = x * x % MOD
      n >>= 1
    end
    ans
  end
end

lines = $stdin.read
array = lines.split("\n")
 
$n = array[0].to_i
$a = array[1].split(" ").map(&:to_i)
 
@comb = Combination.new

dup=$a.sort.each_cons(2).select{|a,b|a==b}.flatten[0]
l,r=$a.index(dup),$a.rindex(dup)
(1..($n+1)).each do |k|
  puts (@comb.choose($n+1,k)-@comb.choose($n+1-(r-l+1),k-1)) % MOD
end

Submission Info

Submission Time
Task D - 11
User hiroyuking
Language Ruby (2.3.3)
Score 600
Code Size 949 Byte
Status
Exec Time 1110 ms
Memory 13800 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 600 / 600 1.txt, mx.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 1110 ms 13800 KB
mx.txt 682 ms 13800 KB
rnd_0.txt 788 ms 12788 KB
rnd_1.txt 593 ms 11984 KB
rnd_2.txt 237 ms 5084 KB
rnd_3.txt 208 ms 4980 KB
rnd_4.txt 255 ms 5644 KB
sample1.txt 29 ms 2684 KB
sample2.txt 29 ms 2684 KB
sample3.txt 30 ms 2684 KB