题目背景

译自 Izborne Pripreme 2016 (Croatian IOI/CEOI Team Selection) D1T1。

「不要忘记，在某个角落始终有个人，为你而战。只要你记住她，你就不是孤身一人。」

提交答案时，采用文件名为 $\texttt{decss-*.out}$。

题目描述

这是一道提交答案题。 输入文件可以在附件中下载。

基本定义

内容扰乱系统（Content Scramble System，CSS）是一种对 DVD 进行加密的技术，以期保护版权。为了方便做题，此题对 CSS 进行了一定的简化。

密钥 $k$ 是一个长度为 $42$ 的 $\texttt{01}$ 序列 $k_1,k_2,\cdots,k_{42}$。

明文、密文是由 $n$ 个字节组成的序列。

密钥流 $T(k)$ 同样是由 $n$ 个字节组成的序列。

加密时，首先基于密钥 $k$ 生成密钥流 $T(k)$，然后将密钥流与明文按位异或，即得到密文。如果已知密文和部分明文，即可得到部分密钥流。

在本题中，你需要基于部分密钥流 $T(k)$ 确定一个可能的密钥 $k$。

---

LFSR

从密钥生成密钥流使用了线性反馈移位寄存器（LFSR）。

LFSR 的状态由 $m$ 位二进制位 $b_1\sim b_m$ 组成。定义反馈位置集 $S\subseteq \{1,2,\cdots,m\}$，它控制输出时会基于哪些位进行运算。

在一个周期内，LFSR 会做如下的事情：

• 输出 $\displaystyle b=\bigoplus_{i\in S} b_i$，其中 $\oplus$ 表示按位异或运算。
• 对于 $1\le i\lt m$，同时令 $b_i\gets b_{i+1}$，并让 $b_m\gets b$。

LFSR 的一步由 $8$ 个周期组成，一步输出一个字节。令这 $8$ 个周期输出的位为 $i_1\sim i_8$，则该步输出的字节为 $(\overline{i_8i_7i_6i_5i_4i_3i_2i_1})_2$。

CSS 使用的 LFSR 有：

名称	$m=$	$S=$	初始状态
LFSR17	$17$	$\{1,15\}$	$k_1,k_2,\cdots,k_{17}$
LFSR25	$25$	$\{1,4,5,13\}$	$k_{18},k_{19},\cdots,k_{42}$

---

生成密钥流

接下来介绍 $T(k)$ 的生成方法。

1. 用 $k$ 将 LFSR17 和 LFSR25 初始化；
2. $c\gets 0$；
3. 重复以下操作 $n$ 次：
   • 令 $x$ 为 LFSR17 执行一步的结果；
   • 令 $y$ 为 LFSR25 执行一步的结果；
   • 令 $z\gets x+y+c$；
   • $c\gets \lfloor z/256\rfloor,z\gets z\bmod 256$；
   • 将 $z$ 新增到密钥流的末尾。

给定部分密钥流，确定一个可能的密钥 $k$，使得它能够生成符合条件的密钥流。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个整数 $t_1,t_2,\cdots,t_n$，描述一个密钥流。

• 如果 $t_i=-1$，表示 $t_i$ 未知。否则 $t_i\in [0,256)$。

输出格式

输出一行一个长度为 $42$ 的 $\texttt{01}$ 串，表示密钥 $k$。

数据保证有解。 输出任意一组合法解均可。

7
154 39 225 99 151 145 -1

011000110010100101100110000000000000111011

提示

评分方式

对于 $100\%$ 的数据，保证 $1\le n\le 500$，保证有解。

令 $m$ 表示已知的密钥流中元素的个数。

输入文件名	$n\le$	$m\le$	得分
$\texttt{decss-1.in}$	$20$	$20$	$8$
$\texttt{decss-2.in}$	$25$	$21$
$\texttt{decss-3.in}$	$20$	$8$
$\texttt{decss-4.in}$	$30$	$10$
$\texttt{decss-5.in}$	$31$	$8$	$9$
$\texttt{decss-6.in}$	$30$	$20$
$\texttt{decss-7.in}$	$200$	$9$	$12$
$\texttt{decss-8.in}$	$300$	$12$
$\texttt{decss-9.in}$	$500$		$13$
$\texttt{decss-10.in}$

样例解释

步数	周期	LFSR17	LFSR25	$x$	$y$	$c$	$z$
初态		1 1100 0110 0101 0010	1 1001 1000 0000 0000 0011 1011			$0$
	1	1 1000 1100 1010 0100	1 0011 0000 0000 0000 0111 0110
	2	1 0001 1001 0100 1000	0 0110 0000 0000 0000 1110 1101
	3	0 0011 0010 1001 0001	0 1100 0000 0000 0001 1101 1011
	4	0 0110 0101 0010 0010	1 1000 0000 0000 0011 1011 0110
	5	0 1100 1010 0100 0100	1 0000 0000 0000 0111 0110 1101
	6	1 1001 0100 1000 1001	0 0000 0000 0000 1110 1101 1011
	7	1 0010 1001 0001 0011	0 0000 0000 0001 1101 1011 0110
	8	0 0101 0010 0010 0111	0 0000 0000 0011 1011 0110 1101
1				$228$	$182$	$1$	$154$
	9	0 1010 0100 0100 1111	0 0000 0000 0111 0110 1101 1011
	10	1 0100 1000 1001 1111	0 0000 0000 1110 1101 1011 0111
	11	0 1001 0001 0011 1110	0 0000 0001 1101 1011 0110 1110
	12	1 0010 0010 0111 1101	0 0000 0011 1011 0110 1101 1101
	13	0 0100 0100 1111 1010	0 0000 0111 0110 1101 1011 1011
	14	0 1000 1001 1111 0100	0 0000 1110 1101 1011 0111 0110
	15	1 0001 0011 1110 1001	0 0001 1101 1011 0110 1110 1101
	16	0 0010 0111 1101 0011	0 0011 1011 0110 1101 1101 1010
2				$203$	$91$	$1$	$39$
	17	0 0100 1111 1010 0110	0 0111 0110 1101 1011 1011 0100
	18	0 1001 1111 0100 1101	0 1110 1101 1011 0111 0110 1001
	19	1 0011 1110 1001 1011	1 1101 1011 0110 1110 1101 0010
	20	0 0111 1101 0011 0111	1 1011 0110 1101 1101 1010 0100
	21	0 1111 1010 0110 1111	1 0110 1101 1011 1011 0100 1000
	22	1 1111 0100 1101 1111	0 1101 1011 0111 0110 1001 0001
	23	1 1110 1001 1011 1110	1 1011 0110 1110 1101 0010 0010
	24	1 1101 0011 0111 1100	1 0110 1101 1101 1010 0100 0101
3				$62$	$162$	$0$	$225$
	25	1 1010 0110 1111 1000	0 1101 1011 1011 0100 1000 1011
	26	1 0100 1101 1111 0001	1 1011 0111 0110 1001 0001 0110
	27	0 1001 1011 1110 0011	1 0110 1110 1101 0010 0010 1101
	28	1 0011 0111 1100 0110	0 1101 1101 1010 0100 0101 1011
	29	0 0110 1111 1000 1100	1 1011 1011 0100 1000 1011 0111
	30	0 1101 1111 0001 1001	1 0111 0110 1001 0001 0110 1111
	31	1 1011 1110 0011 0010	0 1110 1101 0010 0010 1101 1110
	32	1 0111 1100 0110 0101	1 1101 1010 0100 0101 1011 1101
4				$166$	$189$	$1$	$99$