結果

問題 No.147 試験監督（2）
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-11 21:44:36
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,099 ms / 2,000 ms
コード長 1,325 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 28,800 KB
最終ジャッジ日時 2024-06-24 13:30:33
合計ジャッジ時間 5,338 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,092 ms
28,800 KB
testcase_01 AC 1,099 ms
28,800 KB
testcase_02 AC 1,088 ms
28,800 KB
testcase_03 AC 87 ms
12,160 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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?
    if exp.odd?
      r = (r * base) % MOD1097
    end
    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|
    d = d % (MOD1097 - 1) if d > MOD1097 - 1
    result = result * expon(r, d) % MOD1097
  end
  puts result
end
0