[POJ 2065] SETI【高斯消元法】
Problem:
Time Limit: 1000MS | Memory Limit: 30000K |
Description
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
Output
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
Solution:
题目比较长,而且有点难懂。大意是已知 p 和 f(i),求同余方程
- a0 · 10 + a1 · 11 + a2 · 12 + … + an-1 · 1n-1 ≡ f(1) (mod p)
- a0 · 20 + a1 · 21 + a2 · 22 + … + an-1 · 2n-1 ≡ f(2) (mod p)
- a0 · 30 + a1 · 31 + a2 · 32 + … + an-1 · 3n-1 ≡ f(3) (mod p)
- ……
- a0 · n0 + a1 · n1 + a2 · n2 + … + an-1 · nn-1 ≡ f(n) (mod p)
的解 a0 ~ an-1。
构造增广矩阵,预处理 mod p 意义下的逆元(即同余倒数)inv[],将除法转化为乘法。
套用高斯消元即可。
Code: O(nL3) [800K, 32MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int N, p, a[75], f[75], len; int mat[75][75], inv[30000]; char str[75]; inline void Init_inv(){ inv[1] = 1; for(register int i = 2; i < p; i++) inv[i] = (p - p / i) * inv[p % i] % p; } inline int fastpow(int bas, int ex){ int res = 1; while(ex){ if(ex & 1) res = res * bas % p; bas = bas * bas % p; ex >>= 1; } return res; } inline void Gauss_mod(){ for(register int i = 1; i <= len; i++){ int major; for(major = i; major <= len; major++) if(mat[major][i]) break; if(major > len) continue; for(register int j = i; j <= len; j++) swap(mat[major][j], mat[i][j]); for(register int j = len + 1; j >= i; j--) mat[i][j] = mat[i][j] * inv[mat[i][i]] % p; for(register int k = i + 1; k <= len; k++) for(register int j = len + 1; j >= i; j--){ mat[k][j] = (mat[k][j] - mat[k][i] * mat[i][j]) % p; if(mat[k][j] < 0) mat[k][j] += p; } } for(register int i = len; i; i--){ a[i] = mat[i][len + 1]; for(register int j = len; j > i; j--){ a[i] = (a[i] - a[j] * mat[i][j]) % p; if(a[i] < 0) a[i] += p; } } } int main(){ scanf("%d", &N); while(N--){ scanf("%d%s", &p, str + 1), len = strlen(str + 1); Init_inv(); for(register int i = 1; i <= len; i++) f[i] = (str[i] == '*') ? 0 : str[i] - 'a' + 1; for(register int k = 1; k <= len; k++){ for(register int i = 1; i <= len; i++) mat[k][i] = fastpow(k, i - 1); mat[k][len + 1] = f[k]; } Gauss_mod(); for(register int i = 1; i < len; i++) printf("%d ", a[i]); printf("%d\n", a[len]); } return 0; }
发表评论