CodeIQ:「タワー・ビルディング」問題の解答

Kawazoe(@riverplus)さんのCodeIQの問題です。
問題とテストケースはこちらにお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/e574b768cca193ed96af1b5f7a74d7c7
(リンクが切れていました。2025.5.2)
URLが変わっていましたが見つかりました。(2025.5.3追加)
->https://sangaku0418.hatenablog.com/entry/2018/01/04/100100

こちらにも情報があります。
->https://togetter.com/li/1179955

ーーー2025.5.2追加
Aを一辺が1の立方体のブロックとし、
Bを縦が1、横が1、高さが2の直方体のブロックとします。
自然数n,a,b に対し、Aを最大a個、Bを最大b個使って、
縦が1、横が1、高さがnの直方体の塔を作ります。
このときの積み上げ方の場合の数をF(n,a,b)としたとき、
1≦n≦500, 0≦a≦n, 0≦b≦nなる自然数n,a,bに対し、
F(n,a,b)を1000003で割った余りを求める問題です。
ーーー

前回Kawazoeさんの問題は難しいと書きましたが、難しくないものもあります。
漸化式とメモ化で解く方針を立てました。
タワーなのに横に並べて考えたため混乱したのでざっと式変形してみました。
nCrを組み合わせの数として
f(n,a,b)＝Σ(ai+bi)Cai　ただしai+2*bi=n
(ai+bi)Cai=(ai+bi-1)C(ai-1)+(ai+bi-1)Cai=(ai+bi-1)C(ai-1)+(ai+bi-1)C(bi-1)
Σ(ai+bi-1)C(ai-1)+(ai+bi-1)C(bi-1)=f(n-1,a-1,b)+f(n-2,a,b-1)
漸化式はf(n,a,b)=f(n-1,a-1,b)+f(n-2,a,b-1)という当然の結果になりました。
この右辺はタワーの一番上にAを乗せるかBを乗せるかに対応しています。(12月3日)

#julia ver 1.41,1.53,1.73

function solve3(n,a,b,r)
  dic=Dict()
  function f(n,a,b)
    key=string(n)*":"*string(a)*":"*string(b)
    if haskey(dic,key)
      re=dic[key]
    elseif n <0 || a<0 || b<0
      re=0
    elseif n == 0
      re=1
    else
      re=mod(f(n-1,a-1,b)+f(n-2,a,b-1),1000003)
      dic[key]=re
    end
    return re
  end
  ret=mod(f(n,a,b),1000003)
  s = r==ret ? "ok " : "no "
  println(s,ret)
end

solve3(6, 4, 2,11)
solve3(100, 50, 50,765461)
solve3(7, 5, 2,16)
solve3(29, 10, 10,92378)
solve3(500, 249, 125,0)
solve3(123, 81, 82,475012)
solve3(436, 400, 212,544100)
solve3(497, 490, 399,663760)

Juliaでは漸化式で解く方針を立ててましたので式の変形を続けましたがが、
nCrを計算するだけでよいのが明瞭です。prologは遅いしメモ化が面倒なので、
題意に合うaiとbiに対して、(ai+bi)Cbiの合計を計算します。

%Swi-Prolog v 7.4.2,7.6.4

%:-initialization(start).
%start.

ncr(_,0,1).
ncr(N,1,R):-R is N.
ncr(N,M,R):-N1 is N-1,M1 is M-1,ncr(N1,M1,R1),R is R1*N div M,!.

res1(N,A,B,R,R):-
    N>A+2*B,!.
res1(N,A,B,R1,R):- %　N=<A+2*Bの間(N-2*B+B)C(B)を計算してたしていく
    N=<A+2*B,!,X is N-2*B+B,ncr(X,B,R2),R3 is (R1+R2) mod 1000003,
    B1 is B-1,res1(N,A,B1,R3,R).

solve1(A,B,C,D):-
    (res1(A,B,C,0,R)->(R==D->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(R),!.

start:-f1(A,B,C,D),solve1(A,B,C,D),fail.
start.

f1(6, 4, 2,11).
f1(100, 50, 50,765461).
f1(7, 5, 2,16).
f1(29, 10, 10,92378).
f1(500, 249, 125,0).
f1(123, 81, 82,475012).
f1(436, 400, 212,544100).
f1(497, 490, 399,663760).