結果

問題 No.147 試験監督（2）
ユーザー wotsushiwotsushi
提出日時 2017-02-05 17:45:28
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,047 bytes
コンパイル時間 58 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 39,616 KB
最終ジャッジ日時 2024-06-06 14:32:46
合計ジャッジ時間 6,657 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 % 2 == 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 /= 2
        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