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.