TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3129
  • Problem
  • P3129【高斯消元】SETI
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description
    天文学家们一直在监听来自太空的电磁信号.
    最近,他们发现,每条信号可以转换成一系列的整数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)。数据保证有唯一解。
    Input Format

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

    Output Format

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

    Sample Input 1

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

    Sample Output 1

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

    Sample Input 2

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

    Sample Output 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

    Hint

    n<=70
    p<=30000


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