KINV - Dãy nghịch thế độ dài K

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
PROGRAM KINV;
CONST
  FINP='';
  FOUT='';
  maxn=10000;
  maxk=10;
  oo=1000000000;
VAR
  n,k:longint;
  a:array[1..maxn] of longint;
  d:array[1..maxk,1..maxn*6] of longint;
  kq:longint;
procedure readInput;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n,k);
  for i:=1 to n do
    begin
      read(f,a[i]);
      a[i]:=n-a[i]+1;
    end;
  close(f);
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure update(i,l,r,j,k,s:longint);
var
  mid:longint;
begin
  if (l>k) or (r<k) then exit;
  if (l=k) and (r=k) then
    begin
      d[j,i]:=(d[j,i]+s) mod oo;
      exit;
    end;
  mid:=(l+r) div 2;
  update(i shl 1,l,mid,j,k,s);
  update(i shl 1+1,mid+1,r,j,k,s);
  d[j,i]:=(d[j,i shl 1]+d[j,i shl 1+1]) mod oo;
end;
function count(i,l,r,j,k:longint):longint;
var
  mid:longint;
begin
  if r<=k then begin count:=d[j,i]; exit; end;
  if k<l then begin count:=0; exit; end;
  mid:=(l+r) div 2;
  count:=(count(i shl 1,l,mid,j,k)+count(i shl 1+1,mid+1,r,j,k)) mod oo;
end;
procedure solve;
var
  i,j,s:longint;
begin
  for i:=1 to n do
    begin
      update(1,1,n,1,a[i],1);
      if a[i]>1 then
      for j:=2 to k do
        begin
          s:=count(1,1,n,j-1,a[i]-1);
          update(1,1,n,j,a[i],s);
          if j=k then kq:=(kq+s) mod oo;
        end;
    end;
end;
BEGIN
  readInput;
  solve;
  writeOutput;
END.

Download