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.

Download