Description
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?e 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.
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?e 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.
Input
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.
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.
Output
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.
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.
Sample Input
3 31 aaa 37 abc 29 hello*earth
Sample Output
1 0 0 0 1 0 8 13 9 13 4 27 18 10 12 24 15
Source
Northwestern Europe 2004
题意有点难懂，其实就是一个n元n个方程的方程组，那么利用高消来求解。一定有唯一解。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=100;
int MOD;
int x[maxn];
int mat[maxn][maxn];
int free_x[maxn];
int gcd(int a,int b)
{
int t;
while(b)
{
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)
{
memset(x,0,sizeof(x));
memset(free_x,1,sizeof(x));
int i,j,k;
int max_r;
int col,free_index,free_num,ta,tb,temp,LCM;
for(k=0,col=0;k<equ && col<var;k++,col++)
{
max_r=k;
for(i=k+1;i<equ;i++)
{
if(abs(mat[i][col]) > abs(mat[max_r][col]))
max_r=i;
}
if(max_r != k)
{
for(i=k;i<var+1;i++)
swap(mat[k][i],mat[max_r][i]);
}
if(mat[k][col] == 0)
{
k--;
continue;
}
for(i=k+1;i<equ;i++)
{
if(mat[i][col])
{
LCM=lcm(abs(mat[k][col]),abs(mat[i][col]));
ta=LCM/abs(mat[i][col]);
tb=LCM/abs(mat[k][col]);
if(mat[i][col] * mat[k][col] < 0)
tb=-tb;
for(j=col;j<var+1;j++)
mat[i][j]=((mat[i][j]*ta-mat[k][j]*tb)%MOD + MOD)%MOD;
}
}
}
for(i=k;i<equ;i++)
if(mat[i][col])
return -1;
//一定不会有多解
//回代
for(i=var-1;i>=0;i--)
{
temp=mat[i][var];
for(j=i+1;j<var;j++)
if(mat[i][j])
{
temp-=mat[i][j]*x[j];
temp=(temp%MOD+MOD)%MOD;
}
while (temp % mat[i][i] != 0) temp+=MOD;
x[i]=(temp/mat[i][i])%MOD;
}
return 0;
}
char str[maxn];
int kuaisumi(int t,int r)
{
t%=MOD;
int ret=1;
while(r)
{
if(r&1)
{
ret*=t;
ret%=MOD;
}
r>>=1;
t*=t;
t%=MOD;
}
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&MOD,str);
int len=strlen(str);
for(int i=0;i<len;i++)
{
if(str[i]=='*')
mat[i][len]=0;
else
mat[i][len]=str[i]-'a'+1;
for(int j=0;j<len;j++)
mat[i][j]=kuaisumi(i+1,j);
}
int t=Gauss(len,len);
for(int i=0;i<len-1;i++)
printf("%d ",x[i] );
printf("%d\n",x[len-1] );
}
return 0;
}