POJ2065 TOJ1028 ：SETI 高斯消元

r囧r小猫 2022-05-13 14:30 162阅读 0赞

**描述**

For some years, quite a lot of work has been put into listening to electromagnetic radio signals received from space, in order to understand what civilizations in distant galaxies might be trying to tell us. One signal source that has been of particular interest to the scientists at Universit?Le de Technologie Spatiale is the Nebula Stupidicus.  
Recently, it was discovered that if each message is assumed to be transmitted as a sequence of integers a0, a1, ...an-1 the function  f (k) = ∑0<=i<=n-1aiki (mod p) always evaluates to values 0 <= f (k) <= 26 for 1 <= k <= n, provided that the correct value of p is used. n is of course the length of the transmitted message, and the ai denote integers such that 0 <= ai < p. p is a prime number that is guaranteed to be larger than n as well as larger than 26. It is, however, known to never exceed 30 000.  
These relationships altogether have been considered too peculiar for being pure coincidences, which calls for further investigation.  
The linguists at the faculty of Langues et Cultures Extraterrestres transcribe these messages to strings in the English alphabet to make the messages easier to handle while trying to interpret their meanings. The transcription procedure simply assigns the letters a..z to the values 1..26 that f (k) might evaluate to, such that 1 = a, 2 = b etc. The value 0 is transcribed to '\*' (an asterisk). While transcribing messages, the linguists simply loop from k = 1 to n, and append the character corresponding to the value of f (k) at the end of the string.  
The backward transcription procedure, has however, turned out to be too complex for the linguists to handle by themselves. You are therefore assigned the task of writing a program that converts a set of strings to their corresponding Extra Terrestial number sequences.

**输入**

On the first line of the input there is a single positive integer N, telling the number of test cases to follow. Each case consists of one line containing the value of p to use during the transcription of the string, followed by the actual string to be transcribed. The only allowed characters in the string are the lower case letters 'a'..'z' and '\*' (asterisk). No string will be longer than 70 characters.

**输出**

For each transcribed string, output a line with the corresponding list of integers, separated by space, with each integer given in the order of ascending values of i.

**样例输入**

3  
31 aaa  
37 abc  
29 hello\*earth

**样例输出**

1 0 0  
0 1 0  
8 13 9 13 4 27 18 10 12 24 15

高斯消元，求f (k) = ∑0<=i<=n-1aiki (mod p)。

输入字符串str有几个字母代表有几个未知数，\*代表0，a-z代表1-26，用c\[i\]表示第i位代表的数

读入p（模数且为质数），s（下标从0开始），s长度为n  
那么求方程组

![70][]  
的一组合法解

这道题不必判断无解变元（注释部分），题目一定是唯一解。

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    #include<math.h>
    using namespace std;
    #define ll long long
    const int MAXN=500;
    int a[MAXN][MAXN];//增广矩阵
    int x[MAXN];//解集
    int gcd(int a,int b)
    {
        int t;
        while(b!=0)
        {
            t=b;
            b=a%b;
            a=t;
        }
        return a;
    }
    int lcm(int a,int b)
    {
        return a/gcd(a,b)*b;
    }
    int Gauss(int equ,int var,int mod)
    {
        int i,j,k,max_r;// 当前这列绝对值最大的行.
        int col;//当前处理的列
        int temp,ta,tb,LCM;
        col=0; 
        for(k=0;k<equ&&col<var;k++,col++)
        {
            max_r=k;
            for(i=k+1;i<equ;i++)
            {
                if(abs(a[i][col])>abs(a[max_r][col])) 
    			max_r=i;
            }
            if(max_r!=k)
            {
                for(j=k;j<var+1;j++) 
    			swap(a[k][j],a[max_r][j]);
            }
            if(a[k][col]==0)
            {
                k--;
                continue;
            }
            for(i=k+1;i<equ;i++)
            {
                // 枚举要删去的行.
                if(a[i][col]!=0)
                {
                    LCM=lcm(abs(a[i][col]),abs(a[k][col]));
                    ta=LCM/abs(a[i][col]);
                    tb=LCM/abs(a[k][col]);
                    if(a[i][col]*a[k][col]<0)
    				tb=-tb;    //异号的情况是相加
                    for(j=col;j<var+1;j++)
                    {
                        a[i][j]=((a[i][j]*ta-a[k][j]*tb)%mod+mod)%mod;
                    }
                }
            }
        }
        /*for (i=k;i<equ;i++)
        {
            if(a[i][col]!=0) return -1;
        }
        if(k<var)
        {        
            return var-k; 
        }*/
        for(i=var-1;i>=0;i--)
        {
            temp=a[i][var];
            for(j=i+1;j<var;j++)
            {
               temp=((temp-a[i][j]*x[j])%mod+mod)%mod;
    	    }
            while(temp%a[i][i])
            temp+=mod;
            temp/=a[i][i];
            temp%=mod;
            x[i]=temp;
        }
        return 0;
    }
    int main()
    {
        int i,j,equ,var,t,mod,n;
        char str[105];
        scanf("%d",&t);
        while(t--)
        {   	
        	scanf("%d%s",&mod,str);
        	n=strlen(str);
        	equ=var=n;
            memset(a,0,sizeof(a));
            memset(x,0,sizeof(x));
            for(i=0;i<n;i++)
            {
            	if(str[i]=='*')
            		a[i][n]=0;
            	else
            		a[i][n]=str[i]-'a'+1;
            	a[i][0]=1;
                for(j=1;j<n;j++)
                {
                    a[i][j]=(a[i][j-1]*(i+1))%mod;
                }
            }
            int free_num=Gauss(equ,var,mod);
            for(i=0;i<var-1;i++)
            {
                printf("%d ",x[i]);
            }
            printf("%d\n",x[var-1]);
        }
        return 0;
    }

[70]: /images/20220504/a6b85f556dcd4ea79dc79279e6832ba4.png