KINV - Dãy nghịch thế độ dài K
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=10001;
z=1000000000;
var n,re,k:longint;
a:array[1..maxn] of longint;
f:array[1..10,1..maxn] of longint;
procedure rf;
var i:longint;
begin
read(n,k);
for i:=1 to n do read(a[i]);
end;
function calc(j,x:longint):longint;
var r:longint;
begin
r:=0;
while x>0 do
begin
r:=r+f[j,x];
if r>=z then r:=r mod z;
x:=x-x and (-x);
end;
calc:=r;
end;
procedure add(j,x,t:longint);
begin
while x<=maxn do
begin
f[j,x]:=f[j,x]+t;
if f[j,x]>=z then f[j,x]:=f[j,x] mod z;
x:=x+x and (-x);
end;
end;
procedure pr;
var i,t,j,x:longint;
begin
for i:=n downto 1 do
begin
x:=a[i];
t:=calc(k-1,x-1);
re:=re+t;
if re>=z then re:=re mod z;
for j:=k-1 downto 2 do
begin
t:=calc(j-1,x-1);
if t>0 then add(j,x,t);
end;
add(1,x,1);
end;
end;
procedure wf;
begin
writeln(re);
end;
begin
rf;
pr;
wf;
end.