比如剛開始，消第一個(gè)變量，消完之后只讓第一個(gè)方程含有第一個(gè)變量，然后消第二個(gè)變量，消完之后只讓第二個(gè)方程含第二個(gè)變量，以此
關(guān)于自由元指的是這個(gè)變量可以取任何值，得出這樣的結(jié)論是在消變量的過程中發(fā)現(xiàn)該變量的在第row個(gè)方程到第N方程中的系數(shù)都是0了，
求方程的解得過程是從N個(gè)解開始逆推，第N-1個(gè)方程也就包含2個(gè)變量了，第N個(gè)變量和第N-1個(gè)變量，以此下去，就可以解出方程組了。
#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個(gè)解
}
return 1 << (nN - nR);
//返回解的個(gè)數(shù),本題有唯一解
}
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;
}