ac1030.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1030;
const
  maxl=100;
type
  factorlist=record
    count:byte;
    value:array[1..3]of byte;
    e:array[1..3]of byte;
  end;
var
  prime:array[1..maxl]of byte;
  factor:array[1..maxl]of factorlist;
  rep:array['a'..'z']of byte;
  product:array[1..25]of integer;
  primes,n,t,i,ans:longint;
  s:string;
  c:char;
procedure calprime;
  var
    i,j:byte;
  begin
    fillchar(prime,sizeof(prime),1);
    for i:=2 to trunc(sqrt(maxl)) do
      if prime[i]=1 then begin
        j:=i+i;
        while j<=maxl do begin
          prime[j]:=0;
          inc(j,i);
        end;
      end;
    primes:=0;
    for i:=2 to maxl do
      if prime[i]=1 then begin
        inc(primes);
        prime[primes]:=i;
      end;
  end;
procedure calfactor;
  var
    i,t,j:byte;
  begin
    for i:=1 to maxl do begin
      t:=i;j:=1;
      while t>1 do begin
        while t mod prime[j]>0 do inc(j);
        inc(factor[i].count);
        factor[i].value[factor[i].count]:=j;
        repeat inc(factor[i].e[factor[i].count]);t:=t div prime[j];until t mod prime[j]>0;
      end;
    end;
  end;
procedure mul(x,d:shortint);
  var
    i:byte;
  begin
    for i:=1 to factor[x].count do
      inc(product[factor[x].value[i]],factor[x].e[i]*d);
  end;
function res:longint;
  var
    r,i:longint;
  begin
    r:=1;
    for i:=1 to primes do
      r:=r*power(prime[i],product[i]);
    res:=r;
  end;
begin
  calprime;
  calfactor;
  readln(n);
  for t:=1 to n do begin
    readln(s);
    fillchar(rep,sizeof(rep),0);
    for i:=1 to length(s) do
      inc(rep[s[i]]);

    fillchar(product,sizeof(product),0);
    for i:=2 to length(s) do
      mul(i,1);
    for c:='a' to 'z' do
      for i:=2 to rep[c] do
        mul(i,-1);

    ans:=1;
    for i:=1 to length(s) do begin
      mul(length(s)+1-i,-1);
      for c:='a' to pred(s[i]) do
        if rep[c]>0 then begin
          mul(rep[c],1);
          inc(ans,res);
          mul(rep[c],-1);
        end;
      mul(rep[s[i]],1);dec(rep[s[i]]);
    end;
    writeln(ans);
  end;
end.