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.