結果

問題 No.147 試験監督（2）
コンテスト
ユーザー wotsushi
提出日時 2017-02-05 17:46:33
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,050 bytes
コンパイル時間 47 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 43,008 KB
最終ジャッジ日時 2024-12-24 06:38:51
合計ジャッジ時間 12,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
        f1, f2, f3, f4 = 1, 1, 1, 0
        g1, g2, g3, g4 = 1, 0, 1, 0
        while t > 0
          if (t & 1) == 1
            h1 = (g1 * f1 + g2 * f3) % M
            h2 = (g1 * f2 + g2 * f4) % M
            h3 = (g3 * f1 + g4 * f3) % M
            h4 = (g3 * f2 + g4 * f4) % M
            g1 = h1
            g2 = h2
            g3 = h3
            g4 = h4
          end
          h1 = (f1 * f1 + f2 * f3) % M
          h2 = (f1 * f2 + f2 * f4) % M
          h3 = (f3 * f1 + f4 * f3) % M
          h4 = (f3 * f2 + f4 * f4) % M
          f1 = h1
          f2 = h2
          f3 = h3
          f4 = h4
          t >>= 1
        end
        (3 * g1 + 2 * g2) % M
      end
  k = d
  b = x
  a = 1
  while k > 0
    if (k & 1) == 1
      a = (a * b) % M
    end
    b = (b * b) % M
    k >>= 1
  end
  a
}.inject(1) {|memo, item| (memo * item) % M}
puts ans
0