結果

問題 No.147 試験監督（2）
コンテスト
ユーザー らっしー(raccy)
提出日時 2017-03-09 20:27:58
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 827 bytes
コンパイル時間 55 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 36,288 KB
最終ジャッジ日時 2024-06-24 00:14:33
合計ジャッジ時間 6,766 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
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