http://www.lydsy.com/JudgeOnline/problem.php?id=2656
看公式，明显可以折半
当n是偶数时，发现实际要求的是n/2
但是问题在于n为奇数时，他会分叉，两个都算一遍就退化成线性了
那么观察一下
a[n]=a[n/2]+a[n/2+1]
n/2和n/2+1两个之间肯定有一个是奇，一个是偶
若n/2为偶数，那么
a[n/2]=a[n/4]
a[n/2+1]=a[n/4]+a[n/4]+1
若n/2为奇数，那么
a[n/2]=a[(n/2+1)/2-1]+a[(n/2+1)/2]
a[n/2+1]=a[(n/2+1)/2]
可以发现，算偶数项要算的东西，其实算奇数项的时候已经算过了，这样就不用分叉了
首先算一遍所有用到的项数，然后hash一下就好了
program bzoj2656;
const
maxn=100000;
type
gj=array [0..101] of longint;
var
tot,t,i,j,k:longint;
anti:array [0..maxn] of longint;
dl,ans:array [0..801] of gj;
st:string;
now:gj;
function equal (a,b:gj):boolean;
var
i:longint;
begin
if a[0]<>b[0] then exit(false);
for i:=1 to a[0] do
if a[i]<>b[i] then exit(false);
exit(true);
end;
function hash (now:gj):longint;
var
i,k:longint;
begin
k:=0;
for i:=now[0] downto 1 do
k:=(k*10+now[i]) mod maxn;
while (k=0)or((anti[k]<>0)and
(not equal(dl[anti[k]],now))) do
begin
inc(k);
if k=maxn then k:=1;
end;
exit(k);
end;
function divide (a:gj):gj;
var
i:longint;
begin
for i:=a[0] downto 2 do
begin
a[i-1]:=a[i-1]+a[i] mod 2 * 10;
a[i]:=a[i] div 2;
end;
a[1]:=a[1] div 2;
while a[a[0]]=0 do dec(a[0]);
exit(a);
end;
procedure plus (var a:gj);
var
i:longint;
begin
inc(a[1]);
i:=1;
while a[i]=10 do
begin
a[i]:=0;
inc(i);
inc(a[i]);
end;
if a[a[0]+1]<>0 then inc(a[0]);
end;
procedure calc (now:gj);
var
i,j,k,o:longint;
temp:gj;
begin
o:=hash(now);
if anti[o]=0 then
begin
inc(tot);
anti[hash(now)]:=tot;
dl[tot]:=now;
end;
if (now[0]=1)and(now[1]=1) then exit;
if now[1] and 1 = 0 then
begin
temp:=divide(now);
calc(temp);
exit;
end;
now:=divide(now);
if now[1] and 1 = 0 then
begin
o:=hash(now);
if anti[o]=0 then
begin
inc(tot);
dl[tot]:=now;
anti[o]:=tot;
end;
plus(now);
calc(now)
end
else
begin
temp:=now;
plus(temp);
o:=hash(temp);
if anti[o]=0 then
begin
inc(tot);
dl[tot]:=temp;
anti[o]:=tot;
end;
calc(now);
end;
end;
procedure sum (var a,b:gj);
var
i,k:longint;
begin
if a[0]>b[0] then k:=a[0]
else k:=b[0];
for i:=1 to k do
begin
a[i]:=a[i]+b[i];
a[i+1]:=a[i+1]+a[i] div 10;
a[i]:=a[i] mod 10;
end;
if a[k+1]>0 then inc(k);
a[0]:=k;
end;
function over (a,b:gj):boolean;
var
i:longint;
begin
if a[0]>b[0] then exit(true);
if a[0]<b[0] then exit(false);
for i:=a[0] downto 1 do
if a[i]>b[i] then exit(true)
else
if a[i]<b[i] then exit(false);
exit(false);
end;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure qsort (s,e:longint);
var
i,j:longint;
k,temp:gj;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while over(dl[i],k) do inc(i);
while over(k,dl[j]) do dec(j);
if i>j then break;
swap(anti[hash(dl[i])],anti[hash(dl[j])]);
temp:=dl[i];
dl[i]:=dl[j];
dl[j]:=temp;
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
begin
readln(t);
while t>0 do
begin
dec(t);
readln(st);
if st='0' then
begin
writeln(0);
continue;
end;
fillchar(now,sizeof(now),0);
fillchar(anti,sizeof(anti),0);
fillchar(ans,sizeof(ans),0);
fillchar(dl,sizeof(dl),0);
now[0]:=length(st);
for i:=1 to now[0] do
now[i]:=ord(st[now[0]-i+1])-48;
tot:=0;
calc(now);
qsort(1,tot);
ans[tot][0]:=1;
ans[tot][1]:=1;
for i:=tot-1 downto 1 do
if dl[i][1] and 1 = 0 then
begin
now:=divide(dl[i]);
ans[i]:=ans[anti[hash(now)]];
end
else
begin
now:=divide(dl[i]);
ans[i]:=ans[anti[hash(now)]];
plus(now);
sum(ans[i],ans[anti[hash(now)]]);
end;
for i:=ans[1][0] downto 1 do
write(ans[1][i]);
writeln;
end;
end.