poj 2065 SETI(高斯消元求模线性方程组）

题意：

给出一个方程f (k) = ∑0<=i<=n-1aiki (mod p) always evaluates to values 0 <= f (k) <= 26 for 1 <= k <= n ，p给出，f[k]以字符串形式给出，n即字符串的长度，每个字母代表一个f[k], a代表1，b代表2，以此类推，*代表0.让你求出ai并输出。

思路：

方程已经给出，直接建立方程，只要建立方程的过程没有写错，套用下高消求模线性方程组的模板即可，与poj 2947如出一辙，我直接套用那题的高消了，然后就过了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100;
char str[maxn+5];
long long a[maxn+5][maxn+5];
long long solv[maxn+5];
int n, p;
int mod(int x, int y, int p)
{
    int i, res=1;
    for(i=0; i<=y-1; i++)
    {
        res*=x;
        res%=p;
    }
    return res;
}
long long gcd(long long a, long long b)
{
    if(a%b==0)return  b;
    else return gcd(b, a%b);
}
long long lcm(long long a, long long b)
{
    long long g=gcd(a, b);
    return a*b/g;
}
void exgcd(long long a, long long b, long long &d, long long &x, long long &y)
{
    if(!b)
    {
        d=a;
        x=1;
        y=0;
    }
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
void debug()
{
    int i, j;
    for(i=0; i<n; i++)
    {
        for(j=0; j<=n; j++)printf("%lld ", a[i][j]);
        printf("\n");
    }
    return;
}
void gauss()
{

    int col, row, i, j;
    int var=n, equ=n;
    for(col=0, row=0; col<var && row<equ; col++, row++)
    {
        int maxr=row;
        for(i=row+1; i<equ; i++)
        {
            if(a[maxr][col]<a[i][col])maxr=i;
        }
        if(!a[maxr][col])
        {
            row--;
            continue;
        }

        if(a[row][col]==0)   for(j=col; j<=var; j++)swap(a[maxr][col], a[row][col]);
//        debug();
        for(i=row+1; i<equ; i++)
        {
            if(a[i][col])
            {
                int l=lcm(a[i][col], a[row][col]);
                int faca=l/a[i][col], facb=l/a[row][col];
                for(j=col; j<=var; j++)
                {
                    a[i][j]=(a[i][j]*faca)-a[row][j]*facb;
                    a[i][j]=((a[i][j]%p)+p)%p;
                }
            }
        }
    }
//    debug();
    for(i=equ-1; i>=0; i--)
    {
        long long tmp=a[i][var];
        for(j=i+1; j<var; j++)
        {
            tmp=((tmp-a[i][j]*solv[j])%p+p)%p;
        }
        long long d, y;
        exgcd(a[i][i],p, d, solv[i], y);

//       solv[i]=(solv[i]%7+7)%7;
//       printf("%d %d %d\n", solv[i], tmp, d);
        solv[i]=((solv[i]*tmp/d)%p+p)%p;
//       printf("%d\n", solv[i]);
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>p;
        scanf("%s", str);
        int i, j;
        n=strlen(str);
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                a[i][j]=mod(i+1, j, p);
            }
            if(str[i]!='*') a[i][n]=str[i]-'a'+1;
            else a[i][n]=0;
        }
//        debug();
        gauss();
        for(i=0; i<n; i++)
        {
            printf("%lld", solv[i]);
            printf(i==n-1?"\n":" ");
        }
    }
    return 0;
}