luogu#P7693. [CEOI2003] Shift Register

[CEOI2003] Shift Register

题目描述

计算机的寄存器存储 NN 位用于计算。移位寄存器是一种特殊的寄存器,其位值可以很容易地移位一位。
使用反馈移位寄存器,可以通过以下方式生成二进制伪随机数:大小为 NN 的移位寄存器最初填充位值 a1,a2,,aNa_1,a_2,\cdots,a_N。每次,寄存器输出其最右边位的值 aNa_N。其他位值向右移动一个位置。第一个位置被分配一个新值 a1a_1^{\prime},如下所示:
寄存器的每一位都通过一个开关连接到一个异或门(见下图)。对于每个位 ii,有一个开关 sis_i(可以是 1100),用于确定位值 aia_i 是否被转发到 XOR 门。令 ki=si×aik_i = s_i×a_i。新值 a1a_1^{\prime} 被设置为 XOR 门的输出值 XOR(k1,,kNk_1,\cdots, k_N)。注:如果 k1,,kNk_1,\cdots,k_N11 的个数为奇数,则 XOR(k1,,kNk_1,\cdots,k_N)的值为 11,否则为 00)。以下是正式定义:

a1=XOR(k1,,kN)a_1^{\prime} = XOR(k1,\cdots,k_N) ai=ai1 for 2iNa_i^{\prime} = a_{i−1} \text{ for }2 ≤ i ≤ N output=aN\text{output} = a_N

TuLi
在上面的例子中,第一次的值 a1a_1 计算如下:$\text{XOR}(1 \cdot 1,0 \cdot 0,1 \cdot 1,1 \cdot 1,0 \cdot 0,1 \cdot 0,1 \cdot 1) = 0$。 您将获得此类反馈移位寄存器的前 2N2N 个输出值。从这些值中,您将尝试确定开关值 sis_i

输入格式

第一行包含一个整数 NN 为移位寄存器的大小 。第二行包含 2N2N 个数字 0011,它们是移位的前 2N2N 个输出位值。

输出格式

输出只包含一行。如果有一个开关设置产生给定的寄存器输出值,输出任何此类开关设置的开关值 sis_i,从 s1s_1 开始。如果没有这样的开关设置,只输出数字 1-1

7
1 0 0 1 1 0 1 0 1 1 0 0 1 1
1 0 1 1 0 1 1
3
0 0 0 1 1 1
-1

提示

数据规模与约定

对于 100%100 \% 的数据,1N7501 \leq N \leq 750

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2002 的 Shift Register
由 @求学的企鹅 翻译整理。