1 int mod;  2 LL quick(LL a, LL b)  3 {  4     LL ans=1;  5     while(b)  6     {  7         if(b & 1)ans=(ans*a)%mod;  8         a=(a*a)%mod;  9         b>>=1; 10     } 11     return ans%mod; 12 } 13 int gcd(int a, int b) 14 { 15     return b==0? a:gcd(b, a%b); 16 } 17 int lcm(int a, int b) 18 { 19     return a/gcd(a, b)*b; 20 } 21 void ex_gcd(int a, int b, int &x, int &y) 22 { 23     if(b) 24     { 25         ex_gcd(b, a%b, x, y); 26         int tmp=x; 27         x=y; 28         y=tmp-(a/b)*y; 29     } 30     else 31     { 32         x=1, y=0; 33         return ; 34     } 35 } 36  37 int a[300][300];  // 增广矩阵 38 int x[300];  // 解 39 int free_x[300]; // 标记是否为自由未知量 40  41 void Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列 42 { 43     //转换为阶梯形式 44     int col=0, k, num=0; 45     for(k=0; k<n && col<m; k++, col++) 46     { 47         //枚举行 48         int max_r=k; 49         for(int i=k+1; i<n; i++) //找到第col列元素绝对值最大的那行与第k行交换 50             if(abs(a[i][col])>abs(a[max_r][col])) 51                 max_r=i; 52         if(max_r!=k)// 与第k行交换 53             for(int j=col; j<m+1; j++) 54                 swap(a[k][j], a[max_r][j]); 55         if(!a[k][col])// 说明该col列第k行以下全是0了 56         { 57             k--; 58             free_x[num++]=col; 59             continue; 60         } 61         for(int i=k+1; i<n; i++) // 枚举要删除的行 62             if(a[i][col]) 63             { 64                 int LCM=lcm(abs(a[i][col]), abs(a[k][col])); 65                 int ta=LCM/abs(a[i][col]); 66                 int tb=LCM/abs(a[k][col]); 67                 if(a[i][col]*a[k][col]<0) 68                     tb=-tb; 69                 for(int j=col; j<m+1; j++) 70                     a[i][j]=((a[i][j]*ta-a[k][j]*tb)%mod+mod)%mod; 71             } 72     } 73  74     for(int i=k; i<n; i++) 75         if(a[i][col]) 76             return ; // 无解 77  78     if(k<m)   //m-k为自由未知量个数 79         return ; 80          81     //  唯一解 回代 82     for(int i=m-1; i>=0; i--) 83     { 84         int tmp=a[i][m]; 85         for(int j=i+1; j<m; j++) 86         { 87             if(a[i][j]) 88                 tmp-=a[i][j]*x[j]; 89             tmp=(tmp%mod+mod)%mod; 90         } 91         int xx, yy; 92         ex_gcd(a[i][i], mod, xx, yy); 93         xx=(xx%mod+mod)%mod; 94         x[i]=(tmp*xx)%mod; 95     } 96     return ; 97 } 98  99 void init()100 {101     memset(a, 0, sizeof(a));102     memset(x, 0, sizeof(x));103 }104 105 char s[105];106 int main()107 {108     int T;109     while(~scanf("%d", &T))110         while(T--)111         {112             init();113             scanf("%d%s", &mod, s);114             int n=strlen(s);115             for(int i=0; i<n; i++)116             {117                 a[i][n]=(s[i]==‘*‘? 0:s[i]-‘a‘+1);118                 for(int j=0; j<n; j++)119                     a[i][j]=quick(i+1, j);120             }121             Gauss(n, n);122             for(int i=0; i<n; i++)123             {124                 printf("%d", x[i]);125                 if(i==n-1)126                     printf("\n");127                 else128                     printf(" ");129             }130         }131     return 0;132 }