LEM6 - BIRTHDAY

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=80;
  oo=1000000000;
type
  bigNum=array[0..MAXN] of longint;
var
  a:array[1..1011] of longint;
  d:array[0..1,-10..1011] of bigNum;
  m,n:longint;
  f1,f2:text;
operator +(a:bigNum;var b:bigNum) c:bigNum;
var
  nho,i:longint;
begin
  nho:=0;
  fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]);
  for i:=MAXN downto MAXN-c[0]+1 do
    begin
      c[i]:=a[i]+b[i]+nho;
      nho:=c[i] div oo;
      c[i]:=c[i] mod oo;
    end;
  if nho>0 then
    begin
      inc(c[0]);
      c[MAXN-c[0]+1]:=nho;
    end;
end;
procedure print(a:bigNum);
var
  i:longint;
  s:string;
begin
  if a[0]=0 then begin writeln(f2,0); exit; end;
  write(f2,a[MAXN-a[0]+1]);
  for i:=MAXN-a[0]+2 to MAXN do
    begin
      str(a[i],s);
      while length(s)<9 do s:='0'+s;
      write(f2,s);
    end;
  writeln(f2);
end;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,m);
  for i:=1 to m do read(f1,a[i]);
end;
procedure solve;
var
  i,j:longint;
begin
  for i:=-1 to n do
    begin
      d[0,i,0]:=1;
      d[0,i,MAXN]:=1;
    end;
  for i:=1 to m do
    if i mod 2=1 then
      begin
        fillchar(d[1],sizeof(d[1]),0);
        for j:=1 to n do
        if j>=a[i] then
          d[1,j]:=d[1,j-1]+d[0,j-a[i]-1];
      end
    else {i mod 2=1}
      begin
        fillchar(d[0],sizeof(d[0]),0);
        for j:=1 to n do
        if j>=a[i] then
          d[0,j]:=d[0,j-1]+d[1,j-a[i]-1];
      end;
end;
begin
  openF;
  inp;
  solve;
  print(d[m mod 2,n]);
  closeF;
end.

Download