http://poj.org/problem?id=2065
题目是要求
如果str[i] = '*'那就是等于0
求这n条方程在%p下的解。
我看了网上的题解说是高斯消元 + 扩展欧几里德。
然后我自己想了想，就用了高斯消元 ＋ 费马小定理。因为%p是质数，所以很容易就用上了费马小定理，就是在除法的时候用一次就好了。还有就是两个模数相乘还要模一次。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
int p;
const int maxn = 1e2;
char str[maxn];
int quick_pow(int a, int b, int MOD) { //求解 a^b%MOD的值
int base = a % MOD;
int ans = ; //相乘，所以这里是1
while (b) {
if (b & ) {
ans = (ans * base) % MOD; //如果这里是很大的数据，就要用quick_mul
}
base = (base * base) % MOD; //notice。注意这里,每次的base是自己base倍
b >>= ;
}
return ans;
} class GaussMatrix { //复杂度O(n3)
public:
int a[maxn][maxn];
int equ, val; //方程（行）个数，和变量（列）个数，其中第val个是b值，不能取
void init() {
for (int i = ; i <= equ; ++i) {
for (int j = ; j <= val; ++j) {
a[i][j] = 0.0;
}
}
}
void swapRow(int rowOne, int rowTwo) {
for (int i = ; i <= val; ++i) {
swap(a[rowOne][i], a[rowTwo][i]);
}
}
void swapCol(int colOne, int colTwo) {
for (int i = ; i <= equ; ++i) {
swap(a[i][colOne], a[i][colTwo]);
}
}
bool same(int x, int y) {
return x == y;
}
int guass() {
int k, col; // col，当前要处理的列， k当前处理的行
for (k = , col = ; k <= equ && col < val; ++k, ++col) { //col不能取到第val个
int maxRow = k; //选出列最大值所在的行，这样使得误差最小。（没懂）
for (int i = k + ; i <= equ; ++i) {
if (abs(a[i][col]) > abs(a[maxRow][col])) {
maxRow = i;
}
}
if (same(a[maxRow][col], )) { //如果在第k行以后，整一列都是0
--k; //则这个变量就是一个*变量。
continue;
}
if (maxRow != k) swapRow(k, maxRow); // k是当前的最大行了
for (int i = col + ; i <= val; ++i) { //整一列约去系数
// a[k][i] /= a[k][col];
a[k][i] = (a[k][i] * quick_pow(a[k][col], p - , p)) % p;
}
a[k][col] = ; //第一个就要变成1了，然后它下面和上面的变成0
for (int i = ; i <= equ; ++i) {
if (i == k) continue; //当前这行，不操作
for (int j = col + ; j <= val; ++j) { //要使a[i][col] = 0,则需要a[i][col]倍
// a[i][j] -= a[i][col] * a[k][j]; //这一行减去相应的倍数
a[i][j] = (a[i][j] - (a[i][col] * a[k][j]) % p + p) % p;
}
a[i][col] = ;
}
// debug();
}
for (int res = k; res <= equ; ++res) {
if (!same(a[res][val], )) return -; //方程无解
}
return val - k; //*变量个数
}
void debug() {
for (int i = ; i <= equ; ++i) {
for (int j = ; j <= val; ++j) {
printf("%d ", a[i][j]);
}
printf("\n");
}
printf("*******************************************\n\n");
}
} arr;
void init() {
arr.init();
int lenstr = strlen(str + );
arr.equ = lenstr, arr.val = lenstr + ;
int now, to = ;
for (int i = ; i <= lenstr; ++i) {
now = ;
for (int j = ; j <= lenstr; ++j) {
arr.a[i][j] = now;
now = now * to % p;
}
to++;
if (str[i] == '*') arr.a[i][lenstr + ] = ;
else arr.a[i][lenstr + ] = str[i] - 'a' + ;
}
// arr.debug();
}
void work() {
cin >> p >> str + ;
init();
int res = arr.guass();
// assert(res == 0);
int lenstr = strlen(str + );
for (int i = ; i <= lenstr; ++i) {
cout << arr.a[i][lenstr + ] << " ";
}
cout << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) work();
return ;
}