ac1060.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1060;
const
  maxn=6;
  maxp=4;//Something is missing in the TJU description.
         //In the original prob there's a restriction that
         //  sigma|Ki*M^Pi|<=maxlongint, and as 150^5>maxlongint, so maxp=4.
  maxm=150;
  modulo=999983;
  hashsize=modulo+maxm*maxm*maxm;
var
  pow:array[1..maxm,1..maxp]of longint;
  k,p:array[1..maxn]of longint;
  hash,count:array[0..hashsize]of integer;
  next:array[0..hashsize]of longint;
  n,m,i,op,depth,rear,key,ans:longint;
procedure ins(x:longint);
  begin
    key:=abs(x) mod modulo;x:=x div modulo+ord(x>0);
    if count[key]=0 then begin
      hash[key]:=x;count[key]:=1;next[key]:=-1;
    end
    else begin
      while (next[key]>=0) and (hash[key]<>x) do key:=next[key];
      if hash[key]=x then inc(count[key]) else begin
        next[key]:=rear;key:=rear;inc(rear);
        hash[key]:=x;count[key]:=1;next[key]:=-1;
      end;
    end;
  end;
procedure find(x:longint);
  begin
    key:=abs(x) mod modulo;x:=x div modulo+ord(x>0);
    while count[key]>0 do begin
      if hash[key]=x then begin inc(ans,count[key]);exit;end;
      if next[key]<0 then exit;key:=next[key];
    end;
  end;
procedure search(l,s:longint);
  var
    x:byte;
  begin
    if l>depth then
      if op=1 then ins(s) else find(-s)
    else
      for x:=1 to m do
        search(l+1,s+k[l]*pow[x,p[l]]);
  end;
begin
  for m:=1 to maxm do begin
    pow[m,1]:=m;for i:=2 to maxp do pow[m,i]:=pow[m,i-1]*m;
  end;

  repeat
    fillchar(count,sizeof(count),0);rear:=modulo;
    read(n,m);
    for i:=1 to n do read(k[i],p[i]);
    op:=1;depth:=n shr 1;search(1,0);
    ans:=0;op:=2;depth:=n;search(n shr 1+1,0);
    writeln(ans);
  until seekeof;
end.