SETI

 

给出定义f(k) = ∑(0<=i<=n-1)ai*k^i(mod p)，给出n个式子的结果f(1)～f(n)，用一个字符串表示f的值，*表示0，a～z表示1～26，最终要解出a0～a(n-1)

f(1) = a0 * 1^0 + a1 * 1^1 + a2 * 1^2 ,,,,,,,a(n-1) * 1^n

f(2) = a0 * 1^0 + a1 * 2^1 + a2 * 2^2 ,,,,,,,a(n-1) * 2^n

f(3) = a0 * 3^0 + a1 * 3^1 + a2 * 3^2 ,,,,,,,a(n-1) * 3^n

,,,

,,,

f(n) = a0 * n^0 + a1 * n^1 + a2 * n^2 ,,,,,,,a(n-1) * n^n

/*    和poj2947是差不多的，只是多了快速幂    求可行系数时设了个p变量，和输入的p重名了，调试了很久，以后不能在这样拉！ */#include
     
      #include
      
       #include
       
        #define maxn 100using namespace std;int n,p,a[maxn][maxn],ans[maxn];char s[maxn];int Pow(int x,int y){    int res=1;    while(y){        if(y&1)res=res*x%p;        x=x*x%p;        y>>=1;    }    return res;}void guass(){    for(int i=1,k=1;i<=n&&k<=n;i++,k++){
   //枚举每个未知量         int pos=n+1;        for(int j=i;j<=n;j++)if(a[j][k]){pos=j;break;}        if(pos>n){k++;i--;continue;}        for(int j=k;j<=n+1;j++)swap(a[i][j],a[pos][j]);        for(int j=i+1;j<=n;j++){
   //将下面每一行的改元都消去             if(!a[j][k])continue;            int tmp=a[j][k];            for(int l=k;l<=n+1;l++){                a[j][l]=a[i][l]*tmp-a[j][l]*a[i][k];                a[j][l]=(a[j][l]%p+p)%p;            }        }    }    for(int i=n;i>=1;i--){        for(int j=i+1;j<=n;j++){            a[i][n+1]-=ans[j]*a[i][j];            a[i][n+1]=(a[i][n+1]%p+p)%p;        }        while(a[i][n+1]%a[i][i])a[i][n+1]+=p;        ans[i]=(a[i][n+1]/a[i][i])%p;    }    for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");}int main(){    freopen("Cola.txt","r",stdin);    int T;    scanf("%d",&T);    while(T--){        memset(a,0,sizeof(a));        scanf("%d%s",&p,s+1);        n=strlen(s+1);        for(int i=1;i<=n;i++){            if(s[i]=='*')a[i][n+1]=0;            else a[i][n+1]=s[i]-'a'+1;            a[i][n+1]%=p;        }        for(int i=1;i<=n;i++)            for(int j=0;j