Hướng dẫn giải của Đếm dãy
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 maxn=4010; maxk=91; base=100000000; digit=8; type bignum=array[0..10] of longint; var n:longint; a:array[0..maxn,0..maxk] of bignum; re:bignum; procedure rf; begin read(n); end; procedure plus(var c:bignum;a,b:bignum); var mem,max,i:longint; begin mem:=0; if a[0]>b[0] then max:=a[0] else max:=b[0]; for i:=1 to max do begin c[i]:=a[i]+b[i]+mem; if c[i]<base then mem:=0 else begin c[i]:=c[i]-base; mem:=1; end; end; if mem>0 then begin inc(max); c[max]:=mem; end; c[0]:=max; end; procedure pr; var i,j:longint; begin fillchar(a,sizeof(a),0); a[0,0,0]:=1; a[0,0,1]:=1; for i:=1 to n do for j:=1 to maxk do if i>=j then begin if i*2=j*(j+1) then begin a[i,j,0]:=1; a[i,j,1]:=1; end else if i*2>j*(j+1) then plus(a[i,j],a[i-j,j],a[i-j,j-1]); end; fillchar(re,sizeof(re),0); for i:=2 to maxk do plus(re,re,a[n,i]); end; procedure wf; var i,t,j:longint; s:string; begin for i:=re[0] downto 1 do begin if i<re[0] then begin str(re[i],s); t:=length(s); for j:=t+1 to digit do write(0); end; write(re[i]); end; end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include<cstdio> const int N = 4000, L = 3; const long long BASE = 1000000000000000000LL; long long f[N + 1][L]; void add(long long a[L], const long long b[L]) { int rem = 0; for(int i = 0; i < L; ++i) { long long t = a[i] + b[i] + rem; if(t >= BASE) rem = 1, t -= BASE; else rem = 0; a[i] = t; } } void print(const long long a[L]) { int p = L - 1; while(p >= 0 && a[p] == 0) --p; if(p < 0) return; if(p == 0) printf("%lld\n", a[p] - 1); else { printf("%lld", a[p]); while(p--) printf("%018lld", a[p] - (p == 0 ? 1 : 0)); printf("\n"); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif int n; scanf("%d", &n); f[0][0] = 1; for(int i = 1; i <= n; ++i) for(int j = n; j >= i; --j) add(f[j], f[j - i]); print(f[n]); return 0; }
Code mẫu của ladpro98
program PBCDEM; uses math,sysutils; const fi=''; maxn=4000; maxD=3; base=qword(trunc(1e18)); log=trunc(ln(base)/ln(10)); type e=record d:longint; cs:array[0..maxD] of qword; end; var f:array[0..maxn,0..300] of e; n,i,j,ii,nn:longint; res:e; nho:qword; inp:text; procedure cong(a,b:e;var c:e); begin nn:=max(a.d,b.d); nho:=0; for ii:=1 to nn do begin nho:=nho+a.cs[ii]+b.cs[ii]; c.cs[ii]:=nho mod base; nho:=nho div base; end; c.d:=nn; if nho>0 then begin inc(c.d); c.cs[c.d]:=nho; end; end; procedure print(var a:e); var n,i,j:longint; s:string; begin n:=max(a.d,1); for i:=n downto 1 do begin s:=IntToStr(a.cs[i]); if i<n then for j:=1 to log-length(s) do write(0); write(s); end; end; begin assign(inp,fi);reset(inp);readln(inp,n);close(inp); f[0,0].d:=1;f[0,0].cs[1]:=1; for i:=1 to n do for j:=1 to n do if j*(j+1)<=2*i then cong(f[i-j,j],f[i-j,j-1],f[i,j]) else break; for i:=2 to j-1 do cong(res,f[n,i],res); print(res); end.
Code mẫu của RR
//Written by RR {$ifdef rr} {$r+,q+} {$mode objfpc} {$inline off} {$else} {$r-,q-} {$mode objfpc} {$inline on} {$endif} uses math; const FINP = ''; FOUT = ''; MAXN = 4000; MAXK = 100; base = 10000000000000000; lbase = 16; type big = array[0..3] of int64; procedure add(a:big; var 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]<base then nho:=0 else begin dec(c[i],base); nho:=1; end; end; if nho>0 then begin inc(c[0]); c[c[0]]:=nho; end; end; var f1,f2 : text; n : longint; f : array[0..MAXN,0..MAXK] of big; res : big; s : string[20]; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure solve; var i,k,gh:longint; begin f[0][0][0]:=1; f[0][0][1]:=1; for i:=1 to n do begin gh:=min(MAXK,i); for k:=1 to gh do add(f[i-k,k],f[i-k,k-1],f[i,k]); end; for k:=2 to MAXK do add(res,f[n,k],res); write(f2,res[res[0]]); for i:=res[0]-1 downto 1 do begin str(res[i],s); while length(s)<lbase do s:='0'+s; write(f2,s); end; end; begin openF; read(f1,n); solve; closeF; end.
Code mẫu của hieult
#include <cstdio> #include <iostream> //#include <conio.h> #define base 100000000 using namespace std; struct solon { int so; int a[10]; }; solon f[4010][100],T,KQ; int n; solon tong (solon A,solon B) { int du = 0; solon C; if(A.so<B.so) { C = A; A = B; B = C; } for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0; C.so = A.so; for(int i = 1;i<=A.so;i++) { C.a[i] = (A.a[i]+B.a[i]+du)%base; du = (A.a[i]+B.a[i]+du)/base; } if(du>0) {C.so++; C.a[C.so] = du;} return C; } void print(solon A) { printf("%d",A.a[A.so]); for(int i = A.so-1;i>=1;i--) printf("%08d",A.a[i]); } int main() { scanf("%d",&n); T.so = 1; T.a[1] = 0; for(int i = 0;i<=4000;i++) for(int j = 0;j<=100;j++) { f[i][j].so = 1; f[i][j].a[1]=0; } KQ = T; f[1][1].so = 1; f[1][1].a[1] = 1; int t; for(int i = 2;i<=n;i++) { t = 0; for(int j=1;;j++) { t += j; if(t>i) break; f[i][j] = tong(f[i-j][j],f[i-j][j-1]); } } t= 1; for(int j = 2;;j++) { t+=j; if(t>n) break; KQ = tong(KQ,f[n][j]); } print(KQ); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program PBCDEM; const maxn = 4000; maxk = 90; maxd = 8; base = 100000000; type arr = array[1..maxd] of integer; var a: array[0..maxn,0..maxk] of arr; res,tmp: arr; s: string; n,i,j,k: integer; procedure add(var x,y,z: arr); var i: integer; begin for i := 1 to maxd - 1 do x[i] := y[i] + z[i]; for i := 1 to maxd - 1 do if x[i] > base then begin inc(x[i + 1]); x[i] := x[i] - base; end; end; procedure solve; begin readln(n); if n < 3 then begin writeln(0); exit; end; fillchar(a, sizeof(a), 0); for i := 0 to n do a[i,1,1] := 1; for k := 2 to maxk do for i := 1 to n do if 2 * i >= k * (k + 1) then add(a[i,k],a[i - k,k - 1],a[i - k,k]); fillchar(res, sizeof(res), 0); for k := 2 to maxk do begin tmp := res; add(res,tmp,a[n,k]); end; k := maxd; while res[k] = 0 do dec(k); write(res[k]); for i := k - 1 downto 1 do begin str(res[i],s); for j := 8 - length(s) downto 1 do write(0); write(s); end; end; begin solve; readln; end.
Code mẫu của khuc_tuan
{$mode delphi} //{$APPTYPE CONSOLE} //{$R+,Q+,S+} uses SysUtils; const MAX = 6; COSO = 100000000; type TData = class a : array[1..MAX] of LongInt; procedure Add(var b : TData); procedure Viet; end; var F : array[1..90,1..4000] of TData; res : TData; t, i, j, n : integer; procedure TData.Add; var n, i : integer; begin n := 0; for i:=1 to MAX do begin n := n + a[i] + b.a[i]; a[i] := n MOD COSO; n := n div COSO; end; end; procedure TData.Viet; var x, k, h, i, j : integer; begin for i:=MAX downto 1 do if a[i]<>0 then begin Write(a[i]); for j:=i-1 downto 1 do begin h := 1; for k:=1 to 7 do h := h * 10; x := a[j]; for k:=7 downto 0 do begin Write(x div h); x := x mod h; h := h div 10; end; end; exit; end; Write(0); end; begin ReadLn(n); for i:=1 to n do for j:=1 to 90 do F[j][i] := TData.Create; for i:=1 to n do F[1][i].a[1] := 1; for i:=2 to 90 do begin for j:=i+1 to n do begin for t:=1 to MAX do F[i][j].a[t] := F[i][j-i].a[t]; F[i][j].Add(F[i-1][j-i]); end; end; res := TData.Create; for i:=2 to 90 do res.Add(F[i][n]); res.Viet; ReadLn; end.
Bình luận