https://togetter.com/li/1079332 の解答

room_and_roof.ml

(* 累乗関数 *)
(* 数でも行列でも使える *)
let rec pow a n op un =     (* opが演算子、unがunit *)
    if n == 0 then un
    else
        let b = pow a (n/2) op un in
        if n mod 2 == 0 then op b b
        else op b (op b a);;
let m = pow 10 6 ( * ) 1;;
(* mod mでの計算の演算子 *)
let (+:) a b = (a + b) mod m;;
let (-:) a b = (a - b) mod m;;
let ( *: ) a b = (a * b) mod m;;

(* 2*2行列を(a, b, c, d)で表す *)
(* 行列の積 *)
let ( *$ ) m1 m2 =
    let (a, b, c, d) = m1 in
    let (e, f, g, h) = m2 in
    (a*:e +: b*:g, a*:f +: b*:h,
             c*:e +: d*:g, c*:f +: d*:h)

let n = int_of_string (read_line)

let mat = (2, 3, 1, 2);;
let idmat = (1, 0, 0, 1);;
let mat_n = pow mat n ( *$ ) idmat;;
let (a, _, _, _) = mat_n;;
print_int ((a *: 2) -: 1)

room_and_roof.py

# (2 + sqrt(3))^n を小数点以下切り捨てたものは
# (2 + sqrt(3))^n + (2 - sqrt(3))^n - 1 と等しい。
# (2 + sqrt(3))^nを展開したときの整数部分をaとすると、
# 2a - 1で求められる。
# 計算には行列を用いる。

n = int(input())
modulus = 10 ** 6

# Z/mZのクラス
def createZm(m):
    class Zm:
        def __init__(self, a):
            self.int = a % m

        def __add__(self, other):
            return Zm((self.int + other.int) % m)

        def __mul__(self, other):
            return Zm((self.int * other.int) % m)

        def __sub__(self, other):
            return Zm((self.int - other.int) % m)

        def __str__(self):
            return str(self.int)

    return Zm

# 行列の積
def matrix_prod(M, N):
    a, b, c, d = M[0][0], M[0][1], M[1][0], M[1][1]
    e, f, g, h = N[0][0], N[0][1], N[1][0], N[1][1]
    return [[a*e + b*g, a*f + b*h],
            [c*e + d*g, c*f + d*h]]

# 行列の累乗
def matrix_power(M, n):
    if n == 0:
        a, b = Zm(1), Zm(0)
        return [[a, b], [b, a]]

    N = matrix_power(M, n//2)
    if n % 2 == 0:
        return matrix_prod(N, N)
    else:
        return matrix_prod(matrix_prod(N, N), M)

Zm = createZm(modulus)
M = [[Zm(2), Zm(3)], [Zm(1), Zm(2)]]
Mn = matrix_power(M, n)
print(Mn[0][0] * Zm(2) - Zm(1))

room_and_roof.rb

require 'matrix'

class Zm
    @@m = 10 ** 6
    def initialize(a)
        @int = a % @@m
    end

    def +(other)
        return Zm.new((@int + other.int) % @@m)
    end

    def *(other)
        return Zm.new((@int * other.int) % @@m)
    end

    def -(other)
        return Zm.new((@int - other.int) % @@m)
    end

    def self.m=(val)
        @@m = val
    end

    def to_s
        return @int.to_s
    end

    attr_reader :int
end

def mat_mul(m1, m2)
    a, b, c, d = m1[0][0], m1[0][1], m1[1][0], m1[1][1]
    e, f, g, h = m2[0][0], m2[0][1], m2[1][0], m2[1][1]
    return [[a*e + b*g, a*f + b*h],
            [c*e + d*g, c*f + d*h]]
end

def power(mat, n, e)
    if n == 0
        return e
    end
    mat2 = power(mat, n/2, e)
    if n % 2 == 0
        return mat_mul(mat2, mat2)
    else
        return mat_mul(mat2, mat_mul(mat2, mat))
    end
end

n = gets.to_i

mat = [[Zm.new(2), Zm.new(3)], [Zm.new(1), Zm.new(2)]]

E = [[Zm.new(1), Zm.new(0)], [Zm.new(0), Zm.new(1)]]

mat_n = power(mat, n, E)
puts mat_n[0][0] * Zm.new(2) - Zm.new(1)