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.
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