Kawazoe(@riverplus)さんのCodeIQの問題です。
「合計が 0 になるのは何通り？」という問題と同じで、こちらの方の問題と
テストケースのデータはここのお世話になりました。解答もあります。
->https://sangaku0418.hatenablog.com/entry/2016/02/18/100100
nを自然数とするとき1からnまでの自然数を並べ、
それぞれの数の左側に+か-を入れて、
計算結果が0になるような組み合わせの数を求める問題です。
普通に大きい方から+と-で再帰をして、
最後に±1が残る場合1を返す方法でできました。
辞書と、残りの数字の総和がその時点での計算結果の絶対値以上という
枝刈が必要です。
また数が大きくなる場合はBigInt型が必要です。
julia ver 1.41,1.53,1.11.5
function solve(n,a)
function fn(n,v)
if haskey(dic,(n,v)) #辞書
return dic[(n,v)]
elseif n == 1
if abs(v) == 1 return 1
else return 0
end
elseif div(n*(n+1),2) < abs(v) return 0 #枝刈り
else
dic[(n,v)] = fn(n-1,v-n) + fn(n-1,v+n)
return big(dic[(n,v)])
end
end
dic= Dict()
x = fn(n,0)
s = a == x ? "ok " : "no "
println(s,x)
end
solve(3,2)
solve(7,8)
solve(8,14)
solve(48,1140994231458)
solve(49,0)
solve(50,0)
solve(100,1731024005948725016633786324)
solve(101,0)
solve(102,0)
solve(103,13252206944539668255309614628)
Prolog
二次元のキーを持つ辞書がわかりませんので（やったことがある気がするのですが）
代わりに二次元配列を使います（functor/3とtwoar/3及びdata/4）。
data/4はdataの入出の両方に使用します。（内容が変数でなければ取り出し）
配列は負のindexがありませんので、0点をdiv(N*(N+1),2)+1に設定します。
swi-prolog v 7.4.2,7.6.4,9.2.9
%:-initialization(start). %(Online Prolog Compiler,ideone.)
%start.
twoar(F,0,_). % two dimension array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V).
fn(N,M,V,F):-V1 is M+V,data(F,N,V1,X),nonvar(X),!.
fn(1,M,V,F):-!,(abs(V)=:=1->R=1;R=0),V1 is M+V,data(F,1,V1,R).
fn(N,M,V,F):-(N*(N+1) div 2)<abs(V),!,V1 is V+M,data(F,N,V1,0).
fn(N,M,V,F):-
N1 is N-1,V1 is V-N,V2 is V+N,fn(N1,M,V1,F),V11 is M+V1,data(F,N1,V11,X1),
fn(N1,M,V2,F), V21 is M+V2,data(F,N1,V21,X2),X is X1+X2,V01 is V+M,data(F,N,V01,X).
solve(N,R):-N1 is (N+1)*N+1, M is N1 div 2 +1, functor(F,x,N),twoar(F,N,N1),
fn(N,M,0,F),data(F,N,M,R).
start:-f(N,A),(solve(N,R)->(R==A->Str=" ok ";Str=" no ");
write(fail)),write(" "),write(Str),writeln(N->R),fail.
start.
f(3,2).
f(7,8).
f(8,14).
f(48,1140994231458).
f(49,0).
f(50,0).
f(100,1731024005948725016633786324).
f(101,0).
f(102,0).
f(103,13252206944539668255309614628).