KINV - Dãy nghịch thế độ dài K
Tác giả: ladpro98
Ngôn ngữ: Pascal
program kinv;
uses math;
const fi='';
maxn=10005;
maxk=11;
base=trunc(1e9);
var a:array[1..maxn] of longint;
bit,f:array[0..maxk,0..maxn] of longint;
inp:text;
res,n,i,j,k:longint;
procedure update(i,j,v:longint);
begin
while j<=n do
begin
bit[i,j]:=(bit[i,j]+v) mod base;
j:=j + j and (-j);
end;
end;
function get(i,j:longint):longint;
var sum:longint;
begin
sum:=0;
while j>0 do
begin
sum:=(sum+bit[i,j]) mod base;
j:=j-j and (-j);
end;
exit(sum);
end;
begin
assign(inp,fi);reset(inp);
readln(inp,n,k);
for i:=1 to n do
begin
read(inp,a[i]);
f[1,i]:=1;
end;
for i:=2 to k do
begin
for j:=n downto 1 do
begin
f[i,j]:=get(i-1,a[j]);
update(i-1,a[j],f[i-1,j]);
end;
end;
for j:=1 to n do res:=(res+f[k,j]) mod base;
write(res);
end.