TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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修改题目描述中的坑爹处