Editorial for Tree Num


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const base=100000000;
type bignum=array[0..10] of longint;
var t,i,j,l,z:integer;
    s:string;
    n:int64;
    a:array[0..65] of bignum;
    re:bignum;

procedure multi(var x:bignum;y:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to y[0] do
     begin
          x[i]:=y[i]*3+mem;
          if x[i]<base then mem:=0
          else
          begin 
               mem:=x[i] div base; x[i]:=x[i] mod base;
          end;
     end;
     x[0]:=i;
     if mem>0 then
     begin
          x[0]:=x[0]+1;
          x[x[0]]:=mem;
     end;
end;

procedure plus(var x:bignum;y,z:bignum);
var i,mem,max:longint;
begin
     mem:=0;
     if z[0]>y[0] then max:=z[0] else max:=y[0];
     for i:=1 to max do
     begin
          x[i]:=z[i]+y[i]+mem;
          if x[i]<base then mem:=0
          else
          begin x[i]:=x[i] mod base; mem:=1; end;
     end;
     x[0]:=max;
     if mem>0 then
     begin
          x[0]:=x[0]+1;
          x[x[0]]:=mem;
     end;
end;

procedure init;
var i:longint;
begin
     fillchar(a,sizeof(a),0);
     a[0,0]:=1; a[0,1]:=1;
     for i:=1 to 65 do
         multi(a[i],a[i-1]);
end;

begin
     init;
     readln(t);
     for i:=1 to t do
     begin
          readln(n);
          fillchar(re,sizeof(re),0);
          j:=0;
          while n>0 do
          begin
               if n and 1 = 1 then plus(re,re,a[j]);
               n:=n shr 1;
               inc(j);
          end;
          for j:=re[0] downto 1 do
          begin
               if j<re[0] then
               begin
                    str(re[j],s);
                    l:=length(s);
                    for z:=l+1 to 8 do write(0);
               end;
               write(re[j]);
          end;
          writeln;
     end;
end.

Code mẫu của RR

{$R-,Q-}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       64;
  scs           =       40;
type
  big           =       array[0..scs] of longint;
procedure add(var a,b,c:big); inline;
    var
      i,nho:longint;
    begin
      nho:=0;
      c[0]:=max(a[0],b[0]);
      for i:=1 to c[0] do
        begin
          c[i]:=a[i]+b[i]+nho;
          if c[i]<10 then nho:=0 else begin c[i]-=10; nho:=1; end;
        end;
      if nho=1 then
        begin
          inc(c[0]);
          c[c[0]]:=1;
        end;
    end;

var
  f1,f2         :       text;
  test          :       longint;
  n             :       qword;
  lt3           :       array[0..64] of big;
  res           :       big;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure init;
    var
      i:longint;
    begin
      lt3[0][0]:=1; lt3[0][1]:=1;
      for i:=1 to 64 do
        begin
          add(lt3[i-1],lt3[i-1],lt3[i]);
          add(lt3[i-1],lt3[i]  ,lt3[i]);
        end;
    end;
procedure solve;
    var
      i:longint;
    begin
      fillchar(res,sizeof(res),0);
      for i:=0 to 64 do
      if (n>>i) and 1=1 then
        add(res,lt3[i],res);
      if res[0]=0 then begin writeln(f2,0); exit; end;
      for i:=res[0] downto 1 do
        write(f2,res[i]);
      writeln(f2);
    end;

begin
  openF;
  init;
  read(f1,test);
  for test:=1 to test do
    begin
      read(f1,n);
      solve;
    end;
  closeF;
end.

Code mẫu của hieult

//#include <conio.h>
#include <stdio.h>
#include <string.h>
#define du 100000000


struct so
{
    int scs,a[10];
};

so f[40];

void print(so A)
{
     int n = A.scs;
     printf("%d",A.a[n]);
     for(int i = n-1;i>=1;i--)
         printf("%08d",A.a[i]);
} 
         /* Tinh Tong */
void sum(so &tong, so b)
{
     so A = tong;

     if(A.scs > b.scs) for(int i = b.scs+1; i <= A.scs; i++) b.a[i] = 0;
     if(b.scs > A.scs) {for(int i = A.scs+1; i <= b.scs; i++) A.a[i] = 0; tong.scs = b.scs;} 
     int nho = 0;
     for(int i = 1; i <= tong.scs ; i++)
     {
             tong.a[i] = (A.a[i] + b.a[i] + nho)%du;
             nho = (A.a[i] + b.a[i] + nho)/du;
             //printf("%c ",a[i]);
     }    
     if(nho > 0){ tong.scs++ ; tong.a[tong.scs] = nho ;}
}


int main()
{   
    unsigned long long n;
    int T,t;
    f[0].scs = 1;
    f[0].a[1] = 1;
    for(long i=1;i<=70;i++)
    {
        int nho = 0;
        f[i].scs = f[i-1].scs;
        for(int j = 1;j<=f[i].scs;j++)
        {
            f[i].a[j] = (f[i-1].a[j]*3+nho)%du;
            nho = (f[i-1].a[j]*3+nho)/du;
        }
        if(nho>0) f[i].a[++f[i].scs] = nho;
    }

    scanf("%d",&T); 
    for(int i=1;i<=T;i++)
      {
      scanf("%llu",&n);
      //printf("%ull\n",n);
      t=0;
      so x;
      x.scs = 1; x.a[1] = 0;
      while(n!=0)
        {
        if(n%2==1)
          sum(x,f[t]);
        n=n/2;
        t++;
        }
     print(x);
     printf("\n");
     }              
    //getch();  
}

Code mẫu của ll931110

{$MODE DELPHI}
Program TREENUM;
Const
  input  = '';
  output = '';
  maxk = 63;
  kmod = 100000000;
Var
  fi,fo: text;
  t,i: integer;
  n: qword;
  d2: array[0..maxk] of qword;
  d3: array[0..maxk,1..5] of integer;
  d: array[1..5] of integer;
  s: array[1..maxk] of integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure gens;
Var
  i,j: integer;
Begin
  d2[0]:= 1;
  For i:= 1 to maxk do d2[i]:= d2[i - 1] * 2;

  Fillchar(d3, sizeof(d3), 0);
  d3[0,1]:= 1;

  For i:= 1 to maxk do
    Begin
      For j:= 1 to 4 do d3[i,j]:= d3[i - 1,j] * 3;
      For j:= 1 to 4 do if d3[i,j] >= kmod then
        Begin
          d3[i,j + 1]:= d3[i,j + 1] + d3[i,j] div kmod;
          d3[i,j]:= d3[i,j] mod kmod;
        End;
    End;
End;

Procedure solve;
Var
  num,i,j,k: integer;
Begin
  num:= 0;
  For i:= maxk downto 0 do if n >= d2[i] then
    Begin
      inc(num);
      s[num]:= i;
      n:= n - d2[i];
    End;

  Fillchar(d, sizeof(d), 0);
  For i:= 1 to num do
    Begin
      k:= s[i];
      For j:= 1 to 4 do d[j]:= d[j] + d3[k,j];
      For j:= 1 to 4 do if d[j] >= kmod then
        Begin
          d[j + 1]:= d[j + 1] + d[j] div kmod;
          d[j]:= d[j] mod kmod;
        End;
    End;
End;

Procedure printresult;
Var
  st: string;
  i,j,k: integer;
Begin
  k:= 4;
  While d[k] = 0 do dec(k);
  Write(fo, d[k]);

  For i:= k - 1 downto 1 do
    Begin
      str(d[i], st);
      For j:= length(st) + 1 to 8 do write(fo, 0);
      Write(fo, st);
    End;

  Writeln(fo);
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  gens;

  Readln(fi, t);
  For i:= 1 to t do
    Begin
      Readln(fi, n);
      solve;
      printresult;
    End;

  closefile;
End.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.