Description

卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在m个月后有k对兔子，以便分给他们的好友，他的愿望是否能够实现呢？ [任务] 编写一个程序： 从输入文件中读入输入信息； 计算m个月后卡卡将有多少对兔子，设之为P； 计算如果m个月后卡卡要拥有至少k对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为Q； 将结果输出至输出文件。

Input

输入文件的第一行有4个正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。

Output

你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。

Sample Input

0 1 1 10

10000

Sample Output

89

113

HINT

0 < = a < = b < = c< = 100, 1 < = m < = 3 000, 1 < = k < = 10^ 6 000

裸高精度，可压7位。

第二问就是k除以第m天兔子数向上取整，为了防止TLE，我们用倍增法：

先用O(N)时间计算出所有的2^i * Fm的值(记为t[i])，顺便计算出2^i，使2^i恰好大于等于Fm。记bigg为t[Maxi]-Fm，nowans=2^maxi

接着从i-1到0依次bigg减去t[i](如果减去还能为非负的话)，若能减去，则nowans减去2^i.最后2^i就是答案。

这题卡常数非常紧，空间也要安排好。看程序吧。

program p1265;//by htfy96 http://www.cnblogs.com/htfy/ htfy96@qq.comConst u:array[0..8] of longint=(1,10,100,1000,10000,100000,1000000,10000000,100000000); obit=7; bit=10000000;Type gjd=record   len:longint;   d:array[0..1600] of longint; end; Var a,b,c,m,i:longint; f:array[0..3] of gjd; k,one,o,ans,y,bigg:gjd; t:array[0..20000] of gjd; two:gjd; Function big(a,b:gjd):boolean;forward;Function small(a,b:gjd):boolean;forward;procedure print(P:gjd);forward;Function max(a,b:longint):longint;  begin  if a>b then exit(a) else exit(b);end;Procedure fopen;  begin  assign(input,'kacci.in');  assign(output,'kacci.out');  reset(input);  rewrite(output);end;Procedure fclose;  begin  close(input);  close(output);end;Procedure initgjd(var p:gjd;q:longint);  begin  fillchar(p.d,sizeof(p.d),0);  p.len:=1;  p.d[1]:=q;end;Function cheng(p:gjd;q:longint):gjd;var i,jw:longint;  begin  cheng:=p;  jw:=0;  for i:=1 to cheng.len do    begin    cheng.d[i]:=cheng.d[i]*q+jw;    jw:=cheng.d[i] div bit;    cheng.d[i]:=cheng.d[i] mod bit;  end;  if jw>0 then    begin    inc(cheng.len);    cheng.d[cheng.len]:=jw;  end;end;procedure AddP(var p1:gjd;p2:gjd);var i,jw:longint;  begin  p1.len:=max(p1.len,p2.len)+2;  jw:=0;  for i:=1 to p1.len do    begin    p1.d[i]:=p1.d[i]+p2.d[i]+jw;    jw:=p1.d[i] div bit;    p1.d[i]:=p1.d[i] mod bit;  end;  while (p1.len>1) and (p1.d[p1.len]=0) do dec(p1.len);end;Function add(p1,p2:gjd):gjd;var i,jw:longint;  begin  add.len:=max(p1.len,p2.len)+2;  jw:=0;  for i:=1 to add.len do    begin    add.d[i]:=p1.d[i]+p2.d[i]+jw;    jw:=add.d[i] div bit;    add.d[i]:=add.d[i] mod bit;  end;  for i:=add.len+1 to 1600 do add.d[i]:=0;  while (add.len>1) and (add.d[add.len]=0) do dec(add.len);end;Function minus(p1,p2:gjd):gjd;var i:longint;  begin  minus:=p1; // if big(p2,p1) then begin print(p1);print(p2); writeln('overflow!');fclose;halt;end;  for i:=1 to minus.len do    begin    minus.d[i]:=minus.d[i]-p2.d[i];    if minus.d[i]<0 then      begin      inc(minus.d[i],bit);      dec(minus.d[i+1],1);    end;  end;  while (minus.len>0) and (minus.d[minus.len]=0) do dec(minus.len);end;Procedure print(P:gjd);var i:longint;  begin  //writeln('len=',p.len);  for i:=p.len downto 1 do    if i=p.len then write(p.d[i]) else      begin      if p.d[i]<10 then write(0);      if p.d[i]<100 then write(0);      if p.d[i]<1000 then write(0);      if p.d[i]<10000 then write(0);      if p.d[i]<100000 then write(0);      if p.d[i]<1000000 then write(0);      write(p.d[i]);    end;  writeln;end;procedure readgjd(var p:gjd);var ct,newct,w,i:longint; t:array[0..6003] of longint; c:char;  begin  fillchar(p.d,sizeof(p.d),0);  p.len:=0;  ct:=0;  while not eoln do    begin    inc(ct);    read(c);    w:=ord(c)-ord('0');    t[ct]:=w;  end;  for i:=ct downto 1 do    begin    newct:=ct-i+1;    //writeln('i=',i,' newct=',newct,' t[i]=',t[i],' p.len=',(newct-1) div 4+1);    p.len:=(newct-1) div obit+1;    inc(p.d[p.len],t[i]*u[(newct-1) mod obit]);  end;end;Function cheng(p1,p2:gjd):gjd;var i,j,jw:longint;  begin  cheng.len:=p1.len+p2.len;  fillchar(cheng.d,sizeof(cheng.d),0);  for i:=1 to p1.len do    for j:=1 to p2.len do      inc(cheng.d[i+j-1],p1.d[i]*p2.d[j]);  jw:=0;  for i:=1 to cheng.len do    begin    cheng.d[i]:=cheng.d[i]+jw;    jw:=cheng.d[i] div bit;    cheng.d[i]:=cheng.d[i] mod bit;  end;  while (cheng.len>1) and (cheng.d[cheng.len]=0) do dec(cheng.len);end;Function big(a,b:gjd):boolean;var i:longint;  begin  if a.len>b.len then exit(true);  if a.len
     
      b.d[i] then exit(true);    if a.d[i]
      
       b.len then exit(false);  for i:=a.len downto 1 do    begin    if a.d[i]
       
        b.d[i] then exit(false);  end;  exit(false);end;Function div2(P:gjd):gjd;var i,jw:longint;  begin  div2:=p;jw:=0;  for i:=p.len downto 1 do    begin    div2.d[i]:=div2.d[i]+jw*bit;    jw:=div2.d[i] mod 2;    div2.d[i]:=div2.d[i] div 2;  end;  while (div2.len>1) and (div2.d[div2.len]=0) do dec(div2.len);end;Function divide:gjd;var i,now:longint;  begin  t[0]:=o;  now:=0;  initgjd(two,1);    while small(t[now],k) do    begin    inc(now);    t[now]:=Add(t[now-1],t[now-1]);    two:=add(two,two);  end;    y:=t[now];  ans:=two;  bigg:=minus(y,k);  for i:=now-1 downto 0 do    begin    two:=div2(two);    if not small(bigg,t[i]) then      begin      bigg:=minus(bigg,t[i]);      ans:=minus(ans,two);    end;  end;  exit(ans);end;    begin  fopen;  readln(a,b,c,m);  initgjd(f[1],1);  initgjd(f[2],a+1);  initgjd(f[3],a*a+b+a+1);  for i:=4 to m+1 do    begin    f[i mod 4]:=f[(i-1) mod 4];    AddP(f[i mod 4],Cheng(minus(f[(i-1) mod 4],f[(i-2) mod 4]),a));    AddP(f[i mod 4],Cheng(minus(f[(i-2) mod 4],f[(i-3) mod 4]),b));    AddP(f[i mod 4],Cheng(f[(i-3) mod 4],c));  end;        print(f[(m+1) mod 4]);  o:=f[(m+1) mod 4];  readgjd(k);  ans:=divide;  print(ans);  fclose;end.