プロジェクトオイラー Problem 237 「4 × n のゲーム盤上を進む順路」 †

Problem 237 「4 × n のゲーム盤上を進む順路」 †

T(n) を以下のルールに従い 4 × n のゲーム盤上を進む順路の数と定義する:

• 左上の角から始める
• 1マス分の上下左右の移動を繰り返す
• 各マスを全てちょうど1回ずつ通る
• 左下の角で終わる

下の図は 4 × 10 の盤上の順路の一例である:

T(10) は 2329 である. T(1012) を 108 で割った余りを求めよ.

解法
一列ずつの動的計画法でまず計算をしてみました。
次に1列を2つつなげて2列
2列を二つつなげて4列
4列を二つつなげて8列、、、
としてあとは１，２，4,8、、、列を結合して10＾12-２列を作ります。
最初の列とそれをつなげて最後の一列は実行結果を目視で確認して足し算。
最新バージョンのＳＷＩＰｒｏｌｏｇでは10＾12や10＾8でエラーが出るようです。

integer(10^12)-2などのようにして囲む必要があるようです。
おそらく高速化のためだと思いますが個人的には不便になっただけな気がします。
数千桁や数万桁をシームレスにあつかえてこそのＰｒｏｌｏｇだと思うのですが。



記述言語
Ｐｒｏｌｏｇ


datas(X):-
      X=[[[1,2,3,4],[1,2,3,4],1],
         [[1,4,3,2],[1,4,3,2],1],
         [[3,2,1,4],[3,2,1,4],1],
         [[1,0,0,2],[1,2,3,4],1],
         [[1,0,0,2],[1,2,0,0],1],
         [[1,4,3,2],[1,0,0,2],1],
         [[3,2,1,4],[1,0,0,2],1],
         [[1,2,0,0],[1,0,0,2],1],
         [[1,0,0,2],[0,1,2,0],1],
         [[1,0,0,2],[0,0,1,2],1],
         [[1,0,2,0],[0,1,0,2],1],
         [[0,1,2,0],[1,0,0,2],1],
         [[0,1,0,2],[1,0,2,0],1],
         [[0,0,1,2],[1,0,0,2],1],
         [[1,2,0,0],[1,4,3,2],1],
         [[0,0,1,2],[3,2,1,4],1],
         [[1,2,3,4],[0,0,1,2],1],
         [[1,2,3,4],[1,2,0,0],1],
         [[1,4,3,2],[1,0,0,2],1]].

union_sumB([],[E,E1,Count],[[E,E1,Count]]):-!.
union_sumB([[E,E1,Count]|Rest],[E,E1,Count1],Result):-
      !,
      Count2 is (Count+Count1) mod 10^8,
      union_sumB(Rest,[E,E1,Count2],Result).
union_sumB([E|Rest],E1,[E1|Result]):-
      !,
      union_sumB(Rest,E,Result).


union_sum([],[E,Count],[[E,Count]]):-!.
union_sum([[E,Count]|Rest],[E,Count1],Result):-
      !,
      Count2 is (Count+Count1) mod 10^8,
      union_sum(Rest,[E,Count2],Result).
union_sum([E|Rest],E1,[E1|Result]):-
      !,
      union_sum(Rest,E,Result).

next_calc(Base,Datas,[E1,Count3]):-
      member([E,Count1],Base),
      member([E,E1,Count2],Datas),
      Count3 is Count1*Count2.

next_calc_w(Base,Base3,Datas):-
      findall(E,next_calc(Base,Datas,E),Base1),
      msort(Base1,[Top|Base2]),
      union_sum(Base2,Top,Base3).



next_double(Datas,[E,E2,Count3]):-
      member([E1,E2,Count1],Datas),
      member([E,E1,Count2],Datas),
      Count3 is (Count1*Count2) mod 10^8.

next_double_w(Datas,Datas3):-
      findall(E,next_double(Datas,E),Datas1),
      msort(Datas1,[Top|Datas2]),
      union_sumB(Datas2,Top,Datas3).



dp(0,Base,_):-
      !,
      member([[1,0,0,2],C1],Base),
      member([[1,2,3,4],C2],Base),
      Ans is (C1+C2) mod 10^8,
      write([ans,Ans]).

dp(R,Base,Datas):-
      R mod 2=:=1,
      !,
      R1 is R//2,
      next_calc_w(Base,Base1,Datas),
      next_double_w(Datas,Datas1),
      dp(R1,Base1,Datas1).
dp(R,Base,Datas):-
      !,
      next_double_w(Datas,Datas1),
      R1 is R//2,
      dp(R1,Base,Datas1).

main237:-
      datas(X),
      sort(X,Datas),
      Seed=[[[1,2,0,0],1],[[1,2,3,4],1],
            [[0,1,2,0],1],[[0,0,1,2],1]],
      R is 10,
      R1 is R^12-2,
      dp(R1,Seed,Datas).