KINV - Dãy nghịch thế độ dài K

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program KINV;
const
  input  = '';
  output = '';
  maxn = 10000;
  maxk = 10;
  base = 1000000000;
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: integer;
begin
  partition(1,n);
  for i := 1 to n do a[pos[i]] := i;
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]) mod base;
      x := x - (x and -x);
    end;
  calc := res;
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.

Download