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.

Download