結果

問題 No.147 試験監督（2）
コンテスト
ユーザー wotsushi
提出日時 2017-02-05 16:53:02
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 991 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 41,472 KB
最終ジャッジ日時 2024-12-24 06:34:15
合計ジャッジ時間 13,428 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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
def f(a, n)
  if n == 0
    [[1, 0], [0, 1]]
  else
    b = f(a, n / 2)
    c = [[(b[0][0] * b[0][0] + b[0][1] * b[1][0]) % M, (b[0][0] * b[0][1] + b[0][1] * b[1][1]) % M],
         [(b[1][0] * b[0][0] + b[1][1] * b[1][0]) % M, (b[1][0] * b[0][1] + b[1][1] * b[1][1]) % M]]
    if n % 2 == 0
      c
    else
      [[(c[0][0] * a[0][0] + c[0][1] * a[1][0]) % M, (c[0][0] * a[0][1] + c[0][1] * a[1][1]) % M],
       [(c[1][0] * a[0][0] + c[1][1] * a[1][0]) % M, (c[1][0] * a[0][1] + c[1][1] * a[1][1]) % M]]
    end
  end
end
def g(a, n)
  if n == 0
    1
  else
    b = g(a, n / 2)
    c = b**2 % M
    if n % 2 == 0
      c
    else
      (c * a) % M
    end
  end
end
ans = C.zip(D).map {|c, d|
  x = if c == 1
        2
      elsif c == 2
        3
      else
        a = f([[1, 1], [1, 0]], c - 2)
        3 * a[0][0] + 2 * a[0][1]
      end
  g(x, d)
}.inject(1) {|memo, item| (memo * item) % M}
puts ans
0