#P3557. [Ctsc2014]随机数
[Ctsc2014]随机数
[CTSC2014] 随机数
题目描述
露露向花花和萱萱介绍了一种生成伪随机数列的方法。给定正整数 ,以及 ,对于 ,定义
$$M_n= \begin{cases} 2M_{n-1}, & 2M_{n-1}<2^m,\\ (2M_{n-1}-2^m)\operatorname{xor} x,& 2M_{n-1}\ge2^m. \end{cases}$$其中 表示按位异或。若数列在长度趋于无穷时近似等概率地取遍 到 的值,原题称这样的参数 为“好的”。例如, 时 不满足这一性质。
花花想计算 ,但在输入 的二进制表示时,末尾多输入了 个 ,因此算成了 。萱萱有时记下了正确的下标 ,有时只知道多输入的 的个数及花花记录的结果。请给出正确的 。
输入格式
第一行一个正整数 。第二、三行各有 个以空格分隔的 或 ,分别表示 和 ,均从最低位到最高位排列。第四行一个整数 。
- 时,第五行一个整数 ,表示正确下标。
- 时,第五行一个整数 ,第六行有 个以空格分隔的 或 ,从最低位到最高位表示花花算出的 。
输出格式
输出一行恰有 个字符的二进制串,表示正确的 。从最低位到最高位排列,字符之间没有空格。
样例 #1
10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
0
100
0101111001
样例 #2
10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
1
3
0 1 0 1 1 1 1 1 0 1
0101111001
样例 #3
原赛第三组样例另附于选手目录下的 random/random.in 和 random/random.ans。当前归档缺少这对文件。
数据范围
| 原赛测试点 | 上限 | 上限 | 为“好的” | ||
|---|---|---|---|---|---|
| 1 | 不适用 | 0 | 是 | ||
| 2 | 1 | ||||
| 3–5 | 不适用 | 0 | |||
| 6 | 1 | ||||
| 7–9 | |||||
| 10–12 | |||||
| 13–14 | 不适用 | 0 | |||
| 15–16 | 否 | ||||
| 17–20 |