INCVN - INCSEQ VN

Tác giả: RR

Ngôn ngữ: Pascal

program INCSEQ;
const
  FINP='';
  FOUT='';
  MAXN=10001;
  MAXK=50;
  MAX=100001;
  oo=5000000;
var
  a,c,ind:array[1..MAXN] of longint;
  d:array[1..MAXK,1..MAX] of longint;
  sl,n,k:integer;
  s,count:longint;
procedure inp;
var
  f:text;
  i:integer;
begin
  assign(f,FINP); reset(f);
  readln(f,n,k);
  for i:=1 to n do
      read(f,a[i]);
  close(f);
end;
function get(k,u:longint):longint; inline;
var
  kq,v:longint;
begin
  if u<=0 then exit(0);
  kq:=d[k,u];
  v:=u and (u-1);
  if v>0 then
    begin
      kq:=kq+get(k,v);
      if kq>oo then dec(kq,oo);
    end;
  exit(kq);
end;
procedure update(k,u:longint); inline;
var
  v:longint;
begin
  if u<=0 then exit;
  d[k,u]:=d[k,u]+s;
  if d[k,u]>oo then dec(d[k,u],oo);
  v:=u+u and (-u);
  if v<=MAX then update(k,v);
end;
procedure solve;
var
  j,i:integer;
begin
  count:=0;
  for i:=1 to n do
  begin
    s:=1;
    update(1,a[i]);
    for j:=2 to k do
    begin
      s:=get(j-1,a[i]-1);
      update(j,a[i]);
    end;
    count:=count+s;
    if count>oo then dec(count,oo);
  end;
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,count);
  close(f);
end;

procedure swap(var a,b:longint); inline;
var
  tmp:longint;
begin
  tmp:=a; a:=b; b:=tmp;
end;
procedure sort(l,r:longint); inline;
var
  i,j,mid:longint;
begin
  i:=l; j:=r; mid:=c[l+random(r-l+1)];
  repeat
    while c[i]<mid do inc(i);
    while c[j]>mid do dec(j);
    if i<=j then
      begin
        swap(c[i],c[j]);
        swap(ind[i],ind[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure RR;
var
  i:longint;
begin
  for i:=1 to n do
    begin
      c[i]:=a[i];
      ind[i]:=i;
    end;
  sort(1,n);
  a[ind[1]]:=1; sl:=1;
  for i:=2 to n do
    begin
      if c[i]>c[sl] then
        begin
          inc(sl);
          c[sl]:=c[i];
        end;
      a[ind[i]]:=sl;
    end;
end;

begin
  inp;
  RR;
  solve;
  ans;
end.

Download