C11BC1 – spoj

Đề bài:

---

• http://vn.spoj.com/problems/C11BC1/

Thuật toán:

---

• (đang cập nhập)

Code:

---

• Pascal (http://ideone.com/jR8yEK)

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxk=50;
  base=790972;
var
  f : array[0..maxn,0..maxk] of int64;
  i,j,n,k,m : longint;
  kq : int64;
  a,b : array[1..maxn] of longint;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(n,k);
  for i:=1 to n do read(a[i],b[i]);
  close(input);
end;
procedure swap(var x,y: longint);
var tg : longint;
begin
  tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r : longint);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=b[(l+r) div 2];
    repeat
      while x>b[i] do inc(i);
      while xj;
    if il then qs(l,j);
  end;
function muk(x : longint) : int64;
  var i : longint;
  begin
    muk := 1;
    for i:=1 to k do muk:=muk*x;
  end;
function cnk(n,k : longint) : int64;
  begin
    cnk := 1;
    for i:=n-k+1 to n do cnk := cnk*i;
    for i:=1 to k do cnk := cnk div i;
  end;
function tinh : int64;
begin
  fillchar(f,sizeof(f),0);
  for i:=0 to m do f[i,0] := 1;
  for i:=1 to m do
    for j:=1 to min(k,i) do
      f[i,j] := (f[i-1,j] + f[i-1,j-1]*a[i]) mod base;
  exit(f[m,k]);
end;
procedure process;
var i,j,dem : longint;
    dau,cuoi : longint;
begin
  qs(1,n);
  m := n;
  kq := tinh;
  dau := 1;
  while (dau<=n) do
  begin
    cuoi := dau+1;
    m := 1; a[1] := a[dau];
    while (cuoi<=n) and (b[cuoi]=b[dau]) do
      begin
        m := m+1;
        a[m] := a[cuoi];
        inc(cuoi);
      end;
    if cuoi-dau>=k then
      kq := (kq - tinh + base + base) mod base;
    dau := cuoi;
  end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(kq);
  close(output);
end;
begin
  enter;
  process;
  print;
end.