題意比較糾結，搜索了把題意。
給你一個素數P(P<=30000)和一串長為n的字符串str[]。字母'*'代表0，字母a-z分別代表1-26，這n個字符所代表的數字分別代表
f(1)、f(2)....f(n)。定義: f (k) = ∑0<=i<=n-1aiki (mod p) (1<=k<=n,0<=ai<P)，求a0、a1.....an-1。題目保證肯定有唯一解。
解題思路：高斯消元。根據上面的公式顯然可以列出有n個未知數的n個方程式：
a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)
a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2)
..............
a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n)
然後采用高斯消元法來解上面的方程組即可。
典型的高斯消元題，只是多了個modP，因此計算過程中可能需要擴展歐幾裡德算法。
說下所謂的高斯消元的思路，其實可以參看維基百科，
http://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95，大致過程是一直消變量。
比如剛開始，消第一個變量，消完之後只讓第一個方程含有第一個變量，然後消第二個變量，消完之後只讓第二個方程含第二個變量，以此
下去讓最後的方程含最後一個變量，而且最後一個方程中對於前N-1個變量的系數都是0，這樣就能解出這N個變量了。
關於自由元指的是這個變量可以取任何值，得出這樣的結論是在消變量的過程中發現該變量的在第row個方程到第N方程中的系數都是0了，
所以可以取任何值。判斷無解的方式是，第row+1到第N個方程在高斯消元之後所有的系數必定是0，所以方程的值也必須是0。
求方程的解得過程是從N個解開始逆推，第N-1個方程也就包含2個變量了，第N個變量和第N-1個變量，以此下去，就可以解出方程組了。
具體的可以參照維基百科和代碼仔細分析。還有演算法筆記上也有高斯消元的解釋。
代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX (70 + 10)
int nMatrix[MAX][MAX];
int nAns[MAX];
void InitMatrix(char* szStr, int nN, int nP)
{
memset(nMatrix, 0, sizeof(nMatrix));
for (int i = 0; i < nN; ++i)
{
nMatrix[i][nN] = (szStr[i] == '*' ? 0 : szStr[i] - 'a' + 1);
}
for (int i = 0; i < nN; ++i)
{
int nTemp = 1;
for (int j = 0; j < nN; ++j)
{
nMatrix[i][j] = nTemp;
nTemp = (nTemp * (i + 1)) % nP;
}
}
}
int egcd(int nA, int nB, int& nX, int& nY)
{
if (nA < nB)swap(nA, nB);
if (nB == 0)
{
nX = 1, nY = 0;
return nA;
}
int nRet = egcd(nB, nA % nB, nX, nY);
int nT = nX;
nX = nY;
nY = nT - (nA / nB) * nY;
return nRet;
}
int Gauss(int nN, int nP)
{
int nR, nC;
for (nR = nC = 0; nR < nN && nC < nN; ++nR, ++nC)
{
if (nMatrix[nR][nC] == 0)
{
for (int i = nR + 1; i < nN; ++i)
{
if (nMatrix[i][nC])
{
for (int j = nC; j <= nN; ++j)
{
swap(nMatrix[nR][j], nMatrix[i][j]);
}
break;
}
}
}
if (nMatrix[nR][nC] == 0)
{
nR--; //自由元
continue;
}
int nA = nMatrix[nR][nC];
for (int i = nR + 1; i < nN; ++i)
{
if (nMatrix[i][nC])
{
int nB = nMatrix[i][nC];
for (int j = nC; j <= nN; ++j)
{
nMatrix[i][j] = (nMatrix[i][j] * nA - nMatrix[nR][j] * nB) % nP;
}
}
}
}
for (int i = nR; i < nN; ++i)
{
if (nMatrix[i][nN])
{
return -1;//無解
}
}
int nX, nY;
for (int i = nN - 1; i >= 0; i--)
{
int nSum = 0;
for (int j = i + 1; j < nN; ++j)
{
nSum = (nSum + nMatrix[i][j] * nAns[j]) % nP;
}
nSum = (nMatrix[i][nN] - nSum + nP * nP) % nP;
egcd(nP, (nMatrix[i][i] + nP) % nP, nX, nY);
nY = (nY + nP) % nP;
nAns[i] = (nY * nSum + nP) % nP;//第i個解
}
return 1 << (nN - nR);//返回解的個數,本題有唯一解
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
int nP;
int nN;
char szStr[MAX];
scanf("%d%s", &nP, szStr);
nN = strlen(szStr);
InitMatrix(szStr, nN, nP);
Gauss(nN, nP);
for (int i = 0; i < nN; ++i)
{
printf("%d%s", nAns[i], i == nN - 1 ? "\n" : " ");
}
}
return 0;
}
