「トライアングル・メイズ」問題

締め切りが 2016/09/29 10:00 AM なので，その 1 分後に投稿されるように予約

設問

次のルールで生成される迷路を考えます。

レベル 1 の迷路から始めましょう。レベル 1 の迷路を M1 と呼びます。M1 は、3 つの点を L の字の形につないだものです。
左上の点がスタートで、右下の点がゴールです。

レベル 2 の迷路 M2 は、M1 を 3 つつなげて作ります。
M1 を 1 つ置き、さらにその上と右に 1 つずつ M1 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。

レベル 3 の迷路 M3 は、M2 を 3 つつなげて作ります。
M2 を 1 つ置き、さらにその上と右に 1 つずつ M2 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。

以降同様に、レベル k の迷路 Mk を、レベル k－1 の迷路 Mk－1 を 3 つつなげることで定義します。



さて、この迷路を、点と線をたどってスタートからゴールまで着く方法を考えます。
自然数 n に対し、迷路 Mn を最短距離でゴールするたどり方の数を F(n) と定義します。

例えば F(1) ＝ 1，F(2) ＝ 2 です。



同様に、F(3) ＝ 6，F(4) ＝ 42 です。
さらに、F(10) を 1000003（＝10^6＋3） で割った余りは 998593 となることが確かめられます。

標準入力から、自然数 n（1 ≦ n ≦ 10^8）が与えられます。
標準出力に F(n) を 1000003 で割った余り を出力するプログラムを書いてください。

＝＝＝＝＝

いつもの定石，すなわち，小さな問題の解を求め規則性を見つける。a(n) = a(n-1) * (a(n-1)+1)
ただし，真っ正直に計算するのでは n がばかでかいときには時間が掛かりすぎる。
ここでは，「1000003 で割った余り」を求めよということなので，答えの数列は一度ループにはまると，ループをぐるぐる回ることになるということ（これも定石）。
1~213 はループの外，214 項目の数値と同じ数値は1169 項目と同じになる（これは調べる）。
すなわち，214~1168, 1169~2123, ... は長さ955 のループ（同じ数字列の繰り返し）。

f = function(n) {
    m = 1168
    k = 1000003
    a = numeric(m)
    options(scipen=100)
    a[1] = f1 = 1
    a[2] = f2 = 2
    for (i in 3:m) {
        f3 = ((f2 %% k) * ((f2+1) %% k)) %% k
        a[i] = f3
        f1 = f2
        f2 = f3
    }
    if (n >= 214) {
        n = (n-214) %% 955 + 214
    }
    cat(a[n], " ")
}

> f(10)
998593  

> f(100000000)
342482