题解 UVA1563 SETI

实际上，本题就是高斯消元解同余方程组，就是把原来的除法换成逆元，其他的都一样。

#include
using namespace std;
const int N = 110;
int n, p;
int a[N][N];
char s[N];
int power(int x, int t)
{
    int ret = 1;
    for(; t; t >>= 1, x = x * x % p) if(t & 1) ret = ret * x % p;
    return ret;
}
void build()
{
    for(int i = 0; i < n; ++i)
    {
        if(s[i + 1] == '*') a[i][n] = 0;
        else a[i][n] = s[i + 1] - 'a' + 1;
    }
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i) 
            a[k][i] = power(k + 1, i);
}
void gauss_jordan()
{
    for(int now = 0; now < n; ++now)
    {
        int x = now;
        for(int i = now; i < n; ++i) if(abs(a[i][now]) > abs(a[x][now])) x = i;
        for(int i = 0; i <= n; ++i) swap(a[now][i], a[x][i]);
        int inv = power(a[now][now], p - 2);
        for(int i = now; i <= n; ++i) a[now][i] = a[now][i] * inv % p; // /a[now][now]
        for(int i = 0; i < n; ++i) if(i != now && a[i][now])
        {
            int t = a[i][now]; // a[i][j] = a[i][j] - t * a[now][j]
            for(int j = 0; j <= n; ++j) a[i][j] = ((a[i][j] % p - t * a[now][j] % p) % p + p)% p; 
        }
    }
}
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        memset(a, 0, sizeof(a));
        scanf("%d%s", &p, s + 1); n = strlen(s + 1);
        build();
        gauss_jordan();
        for(int i = 0; i < n - 1; ++i) printf("%d ", a[i][n]);
        printf("%d\n", a[n - 1][n]);
    }
    return 0;
}