poj 2065 高斯消元(取模的方程组)
2024-10-11 05:02:18
SETI
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 1735 | Accepted: 1085 |
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.
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 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.
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
题意:
表示最开始并没有看懂题目是什么意思,那一串字母代表f[i]的值
f(k) = ∑0<=i<=n-1aiki (mod p)转换成方程组便是,
a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)
a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2)
......
a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n)
然后利用高斯消元求解
/*
poj 2065
解对mod取模的方程组
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld; using namespace std;
const int maxn = 105; int equ,var;
int a[maxn][maxn];
int b[maxn][maxn];
int x[maxn];
int free_x[maxn];
int free_num;
int n;
void debug()
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= n; j++)
printf("%d ",a[i][j]);
printf("\n");
}
} int gcd(int a,int b)
{
while(b)
{
int tmp = b;
b = a%b;
a = tmp;
}
return a;
} int lcm(int a,int b)
{
return a/gcd(a,b)*b;
} int Gauss(int mod)
{
int max_r,col,k;
free_num = 0;
for(k = 0,col = 0; k < equ && col < var; k++,col++)
{
max_r = k;
for(int i = k+1; i < equ; i++)
{
if(abs(a[i][col]) > abs(a[max_r][col]))
max_r = i;
}
if(a[max_r][col] == 0)
{
k --;
free_x[free_num++] = col;
continue;
}
if(max_r != k)
{
for(int j = col; j < var+1; j++)
swap(a[k][j],a[max_r][j]); }
for(int i = k + 1; i < equ; i++)
{
if(a[i][col] != 0)
{
int LCM = lcm(abs(a[i][col]),abs(a[k][col]));
int ta = LCM / abs(a[i][col]);
int tb = LCM / abs(a[k][col]);
if(a[i][col] * a[k][col] < 0) tb = -tb;
for(int j = col; j < var+1; j++)
{
a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%mod+mod)%mod;
}
}
} }
for(int i = k; i < equ; i++)
if(a[i][col] != 0)
return -1;
if(k < var) return var-k; for(int i = var-1; i >= 0; i--)
{
ll temp = a[i][var];
for(int 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; } void ini()
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
equ = n;
var = n;
} char str[105];
int main()
{
int T,p;
scanf("%d",&T);
while(T--)
{
scanf("%d",&p);
scanf("%s",str);
n = strlen(str);
ini();
for(int 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(int j=1; j<n; j++)
a[i][j]=(a[i][j-1]*(i+1))%p;
} //debug();
Gauss(p); for(int i = 0; i < n-1; i++)
printf("%d ",x[i]);
printf("%d\n",x[n-1]);
}
return 0;
}
最新文章
- How to install OpenBazaar Server in CentOS7
- magento的url中 去掉多余的目录层级
- vm中centos7配置静态ip访问外网
- vim黏贴代码格式混乱的解决方法
- 【HDOJ】2086 A1 = ?
- SGU 176.Flow construction (有上下界的最大流)
- windows phone:使用sqlite-net
- ZS and The Birthday Paradox
- 区间的关系的计数 HDU 4638 离线+树状数组
- 微信最新跳转浏览器功能源码,实现微信内跳转手机浏览器访问网页url
- 背水一战 Windows 10 (98) - 关联启动: 使用外部程序打开一个文件, 使用外部程序打开一个 Uri
- Linux之目录结构解析
- xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at[转载]
- uvalive 3415 Guardian Of Decency
- constant函数
- HTML5+CSS3整体回顾
- Sql server连接数据库报错相关
- IIS web证书申请与安装
- [AT2567] [arc074_c] RGB Sequence
- Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)