学步园

【题意】

有n组信息，每组信息代表一个方程组，有几个字母代表有几个未知数，

*代表0，a-z代表1-26，用c[i]表示第i位代表的数

方程组第一个方程为(a1*1^0+a2*1^1+...+an*1^(n-1)) mod p=c[1] mod p

第i个为(a1*i^0+a2*i^1+...+an*i^(n-1)) mod p=c[i] mod p

对于任意ai都大于等于0小于p

输出每组方程组的解

【输入】

第一行n，代表n组信息

接下来n行，第一个数为p，即模的数，接下来是一个不超过70位的字符串

【输出】

每组按a1..an的顺序输出解，两数之间用空格分隔

数据保证每组数据只有一解

类似poj2947

唯一不同的就是模的数会变化，但是值得庆幸的是不用判无解还是多解还是一解了……

老样子从上到下消元，消完元枚举一下值就行了……

program poj2065;
type
  equation=array [0..71] of longint;
var
  i,j,k,n,t,p,q,x,y,z:longint;
  temp:string;
  line:array [0..71] of equation;
  con,point:array [0..71] of longint;
  space:char;

procedure swap_equation (var a,b:equation);
var
  i:equation;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure swap_int (var a,b:longint);
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure swap (a,b:longint);
begin
  swap_equation(line[a],line[b]);
  swap_int(con[i],con[j]);
end;

function gcd (a,b:longint):longint;
begin
  if a mod b = 0 then exit(b)
                 else exit(gcd(b,a mod b));
end;

procedure gauss;
begin
  for i:=1 to n-1 do
    begin
      if line[i][i]=0 then
        for j:=i+1 to n do
          if line[j][i]<>0 then
            begin
              swap(i,j);
              break;
            end;
      for j:=i+1 to n do
        if line[j][i]<>0 then
          begin
            z:=line[i][i] * line[j][i] div gcd(line[i][i],line[j][i]);
            x:=z div line[i][i];
            y:=z div line[j][i];
            con[j]:=((con[j] * y - con[i] * x) mod p + p) mod p;
            for k:=i to n do
              line[j][k]:=((line[j][k] * y - line[i][k] * x) mod p + p) mod p;
          end;
    end;
  for i:=n downto 1 do
    begin
      k:=con[i];
      for j:=i+1 to n do
        k:=((k-line[i][j]*point[j]) mod p + p) mod p;
      for j:=0 to p-1 do
        if j*line[i][i] mod p = k then break;
      point[i]:=j;
    end;
  for i:=1 to n do
    write(point[i],' ');
  writeln;
end;

begin
  readln(t);
  while t<>0 do
    begin
      read(p);
      read(space);
      readln(temp);
      n:=length(temp);
      for i:=1 to n do
        if temp[i]='*' then con[i]:=0
                       else con[i]:=(ord(temp[i])-96) mod p;
      for k:=1 to n do
        begin
          q:=1;
          for i:=1 to n do
            begin
              line[k,i]:=q;
              q:=q*k mod p;
            end;
        end;
      gauss;
      dec(t);
    end;
end.