TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3129
  • 题目
  • P3129【高斯消元】SETI
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    天文学家们一直在监听来自太空的电磁信号.
    最近,他们发现,每条信号可以转换成一系列的整数a0, a1, ...an-1
    该信息可以通过方程来转换:f(k)=∑0<=i<=n-1aiki(mod p), 0<=f(k)<=26, 1<=k<=n, n是电磁信号的长度, 0<=ai<p。p是一个质数,26<p<=30000.
    给你一个素数P和一长为n的字符串str表示电磁信号。其中字母''代表0,字母a-z分别代表1-26,这n个字符所代表的数字分别代表f(1),f(2),...,f(n).
    也就是说若str[i]=='
    ',则f(i)==0,若str[i]=='b',则f(i)==2。
    求一组a0,a1,...,an-1, 使得他们满足所有的f(k)。数据保证有唯一解。

    输入格式

    一行,一个质数和一个字符串str,以空格做间隔

    输出格式

    一行,n个整数,表示所求的a0, a1, ...an-1

    样例输入 1

    样例1:
    31 aaa
    样例2:
    37 abc
    样例3:
    29 hello*earth

    样例输出 1

    样例1:
    1 0 0
    样例2:
    0 1 0
    样例3:
    8 13 9 13 4 27 18 10 12 24 15

    样例输入 2

    67 *****by*william*shakespeare*****

    样例输出 2

    8 8 47 55 57 61 63 8 40 54 15 48 13 18 21 55 37 17 0 8 61 9 63 38 15 15 14 52 11 13 66 15

    提示

    n<=70
    p<=30000


    来源  poj 2065 Northwestern Europe 2004, 感谢nodgd修改题目描述中的坑爹处