結果

問題 No.147 試験監督(2)
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-11 21:44:36
言語 Ruby
(3.2.2)
結果
AC  
実行時間 960 ms / 2,000 ms
コード長 1,325 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 11,488 KB
実行使用メモリ 32,124 KB
最終ジャッジ日時 2023-09-06 19:05:24
合計ジャッジ時間 5,421 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 960 ms
32,104 KB
testcase_01 AC 954 ms
32,124 KB
testcase_02 AC 943 ms
31,916 KB
testcase_03 AC 77 ms
15,340 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