結果

問題 No.147 試験監督（2）
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-09 20:27:58
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 827 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 11,532 KB
実行使用メモリ 35,812 KB
最終ジャッジ日時 2023-09-06 05:33:23
合計ジャッジ時間 6,959 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# frozen_string_literal: true
require 'matrix'

MOD1097 = 10**9 + 7

FIB_INIT = Vector[1, 0]
FIB_MTX = Matrix[[1, 1], [1, 0]]

FIB_POWS = Math.log2(10**18).ceil.succ.times.inject([FIB_MTX]) do |list, i|
  list + [(list.last**2).map { |x| x % MOD1097 }]
end

def expon(base, exp)
  r = 1
  base %= MOD1097
  curr = base
  while exp.positive?
    r = (r * curr) % MOD1097 if exp.odd?
    curr = (curr * curr) % MOD1097
    exp /= 2
  end
  r
end

def fib(n)
  r = 1
  i = 0
  while n.positive?
    if n.odd?
      r *= FIB_POWS[i]
      r = r.map { |x| x % MOD1097 }
    end
    n >>= 1
    i += 1
  end
  (r * FIB_INIT)[1]
end

if $0 == __FILE__
  n = gets.to_i
  table = Array.new(n) { gets.split.map(&:to_i) }

  result = 1
  table.each do |c, d|
    result *= expon(fib(c + 2), d)
    result %= MOD1097
  end
end
puts result
0