結果

問題 No.147 試験監督（2）
コンテスト
ユーザー らっしー(raccy)
提出日時 2017-03-11 21:39:01
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,296 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 28,928 KB
最終ジャッジ日時 2024-06-24 13:25:10
合計ジャッジ時間 5,594 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
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|
    result = result * expon(r, d % (MOD1097 - 1)) % MOD1097
  end
  puts result
end
0