Problem 5107. -- [NEERC2017]Knapsack Cryptosystem

5107: [NEERC2017]Knapsack Cryptosystem

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 3  Solved: 2
[Submit][Status][Web Board]

Description

Alice选择了n个正整数a_1,a_2,...,a_n,满足a_i>a_1+a_2+...+a_{i-1},
一个正整数q,满足q>a_1+a_2+...+a_n,以及一个正整数r,
满足r和q互质,这n+2个正整数将作为Alice的密钥。
之后Alice计算了b_i=(a_i*r) mod q,这n个整数将作为Alice的公钥。
知道了Alice的公钥,Bob可以发n位的信息给Alice。
他计算出s,也就是他的信息中所有1的位置i对应的b_i的和,这s将作为密文。
在本题中,Alice一定会选择q=2^64,而且Bob会将s模2^64计算。
给定公钥以及密文,请还原出原文。

Input

第一行包含一个正整数n(1<=n<=64),表示信息的位数。
接下来n行,每行一个正整数b_i(1<=b_i<2^64),表示公钥。
最后一行包含一个整数s(0<=s<2^64),即密文模2^64的结果。

Output

输出一行n个数,即原文,显然这是一个长度为n的01串。

Sample Input

5
10
20
50
140
420
440

Sample Output

01001

HINT

Source

[Submit][Status]