Snippets

cia_rana 「ルーム・アンド・ルーフ」問題

Created by cia_rana last modified
codeiq.3130.rb
Raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
require "matrix"
D = 10 ** 6

def solve(n)
  b = Matrix[[2, 3], [1, 2]]
  a = Matrix[[1, 0], [0, 1]]
  m = n - 1
  while m > 0
    a = (a*b).map{|e|e%D} if m.odd?
    b = (b*b).map{|e|e%D}
    m /= 2
  end
  (a[0,0]*4 + a[0,1]*2 - 1) % D
end

p solve(gets.to_i)

Comments (0)

HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.