結果

問題 No.1102 Remnants
ユーザー siman
提出日時 2022-11-03 16:27:40
言語 Ruby
(3.4.1)
結果
RE  
実行時間 -
コード長 544 bytes
コンパイル時間 35 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 55,328 KB
最終ジャッジ日時 2024-07-18 01:19:24
合計ジャッジ時間 5,418 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 RE * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class Integer
  def mod_inverse(mod)
    self.pow(mod - 2, mod)
  end
end

N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
MOD = 10 ** 9 + 7

def comb(n, k, memo)
  return memo[n][k] if memo[n][k]

  if k == 0 || n == k
    return 1
  end

  if k == 1 || k == n - 1
    return n
  end

  memo[n][k] = (comb(n - 1, k, memo) * n * (n - k).mod_inverse(MOD)) % MOD
end

memo = Hash.new { |h, k| h[k] = {} }
ans = 0

A.each.with_index(1) do |a, i|
  ans += a * comb(K + i - 1, K, memo) * comb(N - i + K, K, memo)
  ans %= MOD
end

puts ans
0