INCVN - INCSEQ VN

Tác giả: ladpro98

Ngôn ngữ: Pascal

program incvn;
uses    math;
const   base=5000000;
        maxN=10004;
        maxK=55;
        maxV=100010;
var     f:array[0..maxN,0..maxK] of longint;
        a:array[1..maxN] of longint;
        bit:array[0..maxK,0..maxV] of longint;
        n,k,res,mv,i,j,t,p:longint;

procedure update(i,v:longint);
begin
        while i<=mV do
        begin
                inc(bit[p,i],v);
                if bit[p,i]>=base then dec(bit[p,i],base);
                i:=i+i and (-i);
        end;
end;

function get(k:longint):longint;
var     sum:longint;
begin
        sum:=0;
        while k>0 do
        begin
                inc(sum,bit[p,k]);
                if sum>=base then dec(sum,base);
                k:=k-k and (-k);
        end;
        exit(sum);
end;

begin
        readln(n,k);
        p:=1;
        for i:=1 to n do
        begin
                readln(a[i]);
                inc(a[i],2);
                mv:=max(mv,a[i]);
                f[i,1]:=1;
        end;

        for j:=2 to k do
        begin
                for i:=1 to n do
                begin
                        f[i,j]:=get(pred(a[i]));
                        update(a[i],f[i,p]);
                end;
                inc(p);
        end;

        for i:=1 to n do
        begin
                inc(res,f[i,k]);
                if res>=base then dec(res,base);
        end;

        write(res);
end.

Download