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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.