Euler Projesi 237. Soru

4 x n Oyun Tahtasında Turlar

T(n), 4 × n oyun tahtası üzerindeki tur sayısı olsun öyle ki:

• Tur sol üst köşede başlar.
• Tur, yukarı, aşağı, sola veya sağa bir kare olan hareketlerden oluşur.
• Tur her kareye tam olarak bir kez gider.
• Tur, sol alt köşede sona eriyor.

Şekil, 4 × 10 kart üzerinde bir turu göstermektedir:

T(10) değeri 2329 ise T(10¹²) mod 10⁸ kaçtır?
Cevap: 15836928

Python:

m = [[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 0, 1]]

def mul(x, y):
return [[sum(x[i][k] * y[k][j] % 10 ** 8 for k in range(8)) for j in range(8)] for i in range(8)]

def pow(m, n):
if n == 1:
return m
if n % 2 == 0:
mm = pow(m, n // 2)
return mul(mm, mm)
return mul(m, pow(m, n - 1))

mm = pow(m, 10 ** 12 - 2)

x = [1,0,0,1,0,1,1,0]
x = [sum(mm[i][j] * x[j] % 10 ** 8 for j in range(8)) for i in range(8)]
print((x[2] + x[6]) % 10 ** 8)

Maple:

base := [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], 
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 1, 0], 
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1]]

phi:=proc(n,P1,P2) option remember;
local n1:
if n=1 then base[P1][P2]
else n1:=iquo(n,2): return(add(phi(n1,P1,k)*phi(n-n1,k,P2),k=2..10) mod 10**8)
fi end:

phi(10**12,4,1);
  15836928

C++:

#include 
#include 
/*
eight possible transitions
0: 0-> 3<- 0-="" 1:=""> 1<- 2-="" 2:=""> 3<- 1-="" 3:=""> 2<- 0-="" 4:=""> 1<- 2-=""> 3<- 0-="" 5:=""> 3<- 2-=""> 1<- 2-="" 6:=""> 1<- 0-=""> 3<- 7:="" all="" between="" count="" d-="" end="" for="" from="" global="" goal="" if="" int="" level-1="" level="=0)" long="" main="" memcpy="" pass="" power="1;power<=12;power++)" printf="" recursive="" return="" sizeof="" squares="" sum="" t0="" t1="" that="" through="" to="" transition="" ways="" x10="" x="" y="">%d %lld\n",0,7,ways[0][7]);
}

Mathematica:

In[301]:= (* Legal moves (a,b) *)
Timing[
 Clear[T];
 legal = {{1, 3}, {1, 6}, {2, 3}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {3, 
    7}, {4, 3}, {4, 6}, {5, 1}, {5, 5}, {6, 3}, {6, 6}, {7, 4}, {7, 
    7}};
 (T[#[[1]], #[[2]], 1] = 1) & /@ legal;
 T[i_, j_, 1] = 0;
 T[i_, j_, n_] := 
  T[i, j, n] = 
   Mod[Sum[T[i, k, Floor[n/2]] T[k, j, n - Floor[n/2]], {k, 1, 7}], 
    10^8];
 T[n_] := Mod[Total[T[#[[1]], #[[2]], n - 2] & /@ {
      {1, 3}, {2, 3}, {4, 3}, {5, 3}, {7, 3},
      {1, 5}, {2, 5}, {4, 5}, {5, 5}, {7, 5}
      }], 10^8];
 T[1, 3, 10^12]
 ]

Out[301]= {0.172, 15836928}

Basic:

const
    UpperLim: Int64 = 100000000;

procedure P237UtilCleanup;
    begin
    if debugs then
        begin
        debugs := false;
        closefile (p237output)
        end
    end;


type
    A5x5 = array [0..4, 0..4] of Int64;

procedure copyA (VAR A, B: A5x5);
    var
        n, m: integer;

    begin
    for n := 0 to 4 do
        for m := 0 to 4 do
            B [n, m] := A [n, m]
    end;

procedure multAB (VAR A, B, C: A5x5);
    var
        n, i, j: integer;
        v: Int64;

    begin
    for i := 0 to 4 do
        for j := 0 to 4 do
            begin
            v := 0;
            for n := 0 to 4 do
                v := (v + A [i, n] * B [n, j]) mod UpperLim;
            C [i, j] := v
            end
    end;

const
    A: A5x5 = ((1, 0, 0, 1, 0),
                (0, 0, 0, 1, 0),
                (0, 0, 1, 1, 0),
                (1, 1, 1, 1, 99999999), // 99999999 = -1 mod 10^8
                (0, 1, 0, 0, 0));

var
    B, C, D: A5x5;

procedure doThatThing;
    var
        n, m: int64;

    begin
    n := 10 * 10 * 10;
    n := n * n;
    n := n * n;
    CopyA (A, B);
    CopyA (A, C);
    dec (n);
    while n <> 0 do
        begin
        if n mod 2 = 1 then
            begin
            MultAB (C, B, D);
            CopyA (D, C)
            end;
        n := n div 2;
        MultAB (B, B, D);
        CopyA (D, B)
        end;

    form1.Memo1.Lines.Add(format('results = %0d', [C [1, 3]]));
    end;