結果

問題 No.147 試験監督（2）
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-11 21:08:35
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,266 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 44,992 KB
最終ジャッジ日時 2024-06-24 13:20:49
合計ジャッジ時間 7,627 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

# frozen_string_literal: true
MOD1097 = 10**9 + 7

M2x2 = Struct.new(:e00, :e01, :e10, :e11) do
  def multi_own!(other)
    next_e00 = (e00 * other.e00 + e01 * other.e10) % MOD1097
    next_e01 = (e00 * other.e01 + e01 * other.e11) % MOD1097
    next_e10 = (e10 * other.e00 + e11 * other.e10) % MOD1097
    next_e11 = (e10 * other.e01 + e11 * other.e11) % MOD1097
    self.e00 = next_e00
    self.e01 = next_e01
    self.e10 = next_e10
    self.e11 = next_e11
  end
end

def fib(*list)
  fib_mtx = M2x2.new(1, 1, 1, 0)
  result = Array.new(list.size) { M2x2.new(1, 1, 1, 0) }
  check = 1
  Math.log2(10**18).floor.succ.times do
    list.each_with_index do |n, i|
      next if (n & check).zero?
      result[i].multi_own!(fib_mtx)
    end
    fib_mtx.multi_own!(fib_mtx)
    check <<= 1
  end
  result.map(&:e00)
end

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

if $0 == __FILE__
  n = gets.to_i
  table = Array.new(n) { gets.split.map(&:to_i) }
  table_c = table.map(&:first)
  table_d = table.map(&:last)
  result_c = fib(*table_c)
  result = 1
  result_c.zip(table_d).each do |r, d|
    result = result * expon(r, d) % MOD1097
  end
  puts result
end
0