Submission #2640520


Source Code Expand

Copy
MOD = 1_000_000_007

class Combination
  def initialize(size)
    @fact = (1..size).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) % MOD ) % MOD
  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
$k = array[1].to_i
@comb = Combination.new($n+$k)

# nHr => n+r-1Cr
# puts "#{$n}H#{$k}"
ans = @comb.choose($n+$k-1, $n-1)
puts ans

Submission Info

Submission Time
Task D - 多重ループ
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 823 Byte
Status
Exec Time 51 ms
Memory 3452 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt
Subtask1 99 / 99 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
All 1 / 1 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask0_sample_05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 7 ms 1788 KB
subtask0_sample_02.txt 7 ms 1788 KB
subtask0_sample_03.txt 7 ms 1788 KB
subtask0_sample_04.txt 7 ms 1788 KB
subtask0_sample_05.txt 51 ms 3452 KB
subtask1_01.txt 7 ms 1788 KB
subtask1_02.txt 7 ms 1788 KB
subtask1_03.txt 7 ms 1788 KB
subtask1_04.txt 7 ms 1788 KB
subtask1_05.txt 7 ms 1788 KB
subtask1_06.txt 7 ms 1788 KB
subtask1_07.txt 7 ms 1788 KB
subtask1_08.txt 7 ms 1788 KB
subtask1_09.txt 7 ms 1788 KB
subtask1_10.txt 7 ms 1788 KB
subtask1_11.txt 9 ms 1788 KB
subtask1_12.txt 7 ms 1788 KB
subtask1_13.txt 7 ms 1788 KB
subtask1_14.txt 7 ms 1788 KB
subtask1_15.txt 7 ms 1788 KB
subtask1_16.txt 7 ms 1788 KB
subtask1_17.txt 7 ms 1788 KB
subtask1_18.txt 7 ms 1788 KB
subtask1_19.txt 7 ms 1788 KB
subtask2_02.txt 24 ms 2428 KB
subtask2_03.txt 36 ms 2812 KB
subtask2_04.txt 21 ms 2300 KB
subtask2_05.txt 42 ms 3068 KB
subtask2_06.txt 14 ms 2172 KB
subtask2_07.txt 29 ms 2684 KB
subtask2_08.txt 40 ms 3068 KB
subtask2_09.txt 29 ms 2684 KB
subtask2_10.txt 51 ms 3452 KB