結果

問題 No.147 試験監督（2）
ユーザー wotsushi
提出日時 2017-02-05 17:18:08
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 997 bytes
コンパイル時間 44 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 41,088 KB
最終ジャッジ日時 2024-12-24 06:36:48
合計ジャッジ時間 13,003 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

N = gets.to_i
C, D = (1..N).map {gets.split.map(&:to_i)}.transpose
M = 10**9 + 7
ans = C.zip(D).map {|c, d|
  x = if c == 1
        2
      elsif c == 2
        3
      else
        t = c - 2
        z = [[1, 1], [1, 0]]
        y = [[1, 0], [0, 1]]
        while t > 0
          if t % 2 == 1
            y = [[(y[0][0] * z[0][0] + y[0][1] * z[1][0]) % M, (y[0][0] * z[0][1] + y[0][1] * z[1][1]) % M],
                 [(y[1][0] * z[0][0] + y[1][1] * z[1][0]) % M, (y[1][0] * z[0][1] + y[1][1] * z[1][1]) % M]]
          end
          z = [[(z[0][0] * z[0][0] + z[0][1] * z[1][0]) % M, (z[0][0] * z[0][1] + z[0][1] * z[1][1]) % M],
               [(z[1][0] * z[0][0] + z[1][1] * z[1][0]) % M, (z[1][0] * z[0][1] + z[1][1] * z[1][1]) % M]]
          t /= 2
        end
        (3 * y[0][0] + 2 * y[0][1]) % M
      end
  k = d
  b = x
  a = 1
  while k > 0
    if k % 2 == 1
      a = (a * b) % M
    end
    b = b**2 % M
    k /= 2
  end
  a
}.inject(1) {|memo, item| (memo * item) % M}
puts ans
0