INCVN - INCSEQ VN
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program INCVN;
const
input = '';
output = '';
maxn = 10000;
maxk = 50;
base = 5000000;
var
b,pos,a: array[1..maxn] of integer;
t: array[0..maxn,0..maxk] of integer;
n,k: integer;
procedure init;
var
f: text;
i: integer;
begin
assign(f, input);
reset(f);
readln(f, n,k);
for i := 1 to n do
begin
read(f, b[i]);
pos[i] := i;
end;
close(f);
end;
procedure swap(var x,y: integer);
var
z: integer;
begin
z := x;
x := y;
y := z;
end;
procedure quicksort;
procedure partition(l,h: integer);
var
i,j,p: integer;
begin
if l >= h then exit;
i := l; j := h; p := b[random(h - l + 1) + l];
repeat
while b[i] < p do inc(i);
while b[j] > p do dec(j);
if i <= j then
begin
if i < j then
begin
swap(b[i],b[j]);
swap(pos[i],pos[j]);
end;
inc(i);
dec(j);
end;
until i > j;
partition(l,j);
partition(i,h);
end;
var
i,c: integer;
begin
partition(1,n);
c := 1;
a[pos[1]] := 1;
for i := 2 to n do
begin
if b[i] > b[i - 1] then inc(c);
a[pos[i]] := c;
end;
end;
procedure update(x,y,z: integer);
begin
while x <= maxn do
begin
t[x,y] := (t[x,y] + z) mod base;
x := x + (x and -x);
end;
end;
function calc(x,y: integer): integer;
var
res: integer;
begin
if x = 0 then exit(0);
res := 0;
while x > 0 do
begin
res := res + t[x,y];
x := x - (x and -x);
end;
calc := res mod base;
end;
procedure solve;
var
i,j,tmp: integer;
begin
fillchar(t, sizeof(t), 0);
for i := 1 to n do
begin
for j := 2 to k do
begin
tmp := calc(a[i] - 1,j - 1);
update(a[i],j,tmp);
end;
update(a[i],1,1);
end;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, calc(n,k));
close(f);
end;
begin
init;
quicksort;
solve;
printresult;
end.