題目大意：給定一個素數p和一個字符串串str。令f[i] = Num(str[i]),Num(str[i])表示當str[i]為*的時候為0，str[i]為a-z的時候為str[i]-a+1.
接著得到n（str[i]的長度)個方程組，每個方程組格式為(a1*k^0+a2*k^1+...+an*k^(n-1)) mod p = f[k] mod p (1<=k<=n),ai為未知量，讓我們解這個方程組，輸出n個解。
解題思路：比較裸的高斯消元，我抄一抄模板就過掉了，但是讓我講高斯消元的核心思想還是不會講，線代老師死得早啊。
講下我認識的高斯消元類題目一般步驟吧：1、利用題目信息建立方程組 2、將方程組化為增廣矩陣 3、將增廣矩陣化為行階梯矩陣 4、求解。第1步是關鍵也是難點，後面的可以套用模版。具體的分析見這篇文章：
測試數據：
3
29 hello*earth
out: 8 13 9 13 4 27 18 10 12 24 15
C艹代碼：
[cpp]
#include <iostream>
#include <string>
#include <string.h>
#include <cmath>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX 71
char str[MAX];
int n,m,p,x[MAX];
int mat[MAX][MAX];
void Initial() {
int i,j,k = 1;
memset(x,0,sizeof(x));
for (i = 0; i < n; ++i) {
mat[i][m] = str[i]=='*'?0:str[i]-'a'+1;
for (k = 1,j = 0; j < m; ++j)
mat[i][j] = k,k = k * (i + 1) % p;
//for (j = 0; j < m; ++j)
// printf("%d%c",mat[i][j],j==m-1?'\n':' ');
}
}
inline int gcd(int x,int y) {
int r = x % y;
while (r) {
x = y,y = r;
r = x % y;
}
return y;
}
inline int lcm(int x,int y) {
return x/gcd(x,y) * y;
}
void Gauss() {
int i,j,row,max_r,col;
int ta,tb,temp,LCM;
int free_x_num,free_index;
col = row = 0;
for (; row < n && col < m; ++row,++col) {
max_r = row;
for (i = row + 1; i < n; ++i)
if (abs(mat[i][col]) > abs(mat[max_r][col]))
max_r = i;
if (max_r != row)
for (j = row; j <= m; ++j)
swap(mat[row][j],mat[max_r][j]);
if (mat[row][col] == 0) {
row--;
continue;
}
for (i = row + 1; i < n; ++i)
if (mat[i][col] != 0) {
LCM = lcm(abs(mat[i][col]),abs(mat[row][col]));
ta = LCM / abs(mat[i][col]);
tb = LCM / abs(mat[row][col]);
if (mat[i][col] * mat[row][col] < 0)
tb = -tb;
for (j = col; j <= m; ++j)
mat[i][j] = (mat[i][j] * ta - mat[row][j] * tb) % p;
}
}
//printf("yes,you can ac\n");
for (i = m - 1; i >= 0; --i) {
temp = mat[i][m];
for (j = i + 1; j < m; ++j)
if (mat[i][j] != 0)
temp = ((temp - mat[i][j] * x[j])%p + p) % p;
while (temp % mat[i][i]) temp = temp + p;
x[i] = (temp / mat[i][i] + p) % p;
}
}
int main() www.2cto.com
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%d %s",&p,str);
n = strlen(str);
m = n,Initial();
Gauss();
for (i = 0; i < m; ++i)
printf("%d%c",x[i],i==m-1?'\n':' ');
}
}
作者：woshi250hua
