#P3557. [Ctsc2014]随机数

    ID: 2675 传统题 5000ms 400MiB 尝试: 173 已通过: 14 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS多项式与生成函数NTT多项式求逆多项式牛顿迭代多项式除法数论快速幂线性代数与代数域CF3000

[Ctsc2014]随机数

[CTSC2014] 随机数

题目描述

露露向花花和萱萱介绍了一种生成伪随机数列的方法。给定正整数 mm,以及 0≤x,M0<2m0\le x,M_0<2^m,对于 n≥1n\ge1,定义

$$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}$$

其中 xor⁡\operatorname{xor} 表示按位异或。若数列在长度趋于无穷时近似等概率地取遍 11 到 2m−12^m-1 的值,原题称这样的参数 xx 为“好的”。例如,m>1m>1 时 x=0x=0 不满足这一性质。

花花想计算 MkM_k,但在输入 kk 的二进制表示时,末尾多输入了 ll 个 00,因此算成了 Mk 2lM_{k\,2^l}。萱萱有时记下了正确的下标 kk,有时只知道多输入的 00 的个数及花花记录的结果。请给出正确的 MkM_k。

输入格式

第一行一个正整数 mm。第二、三行各有 mm 个以空格分隔的 00 或 11,分别表示 xx 和 M0M_0,均从最低位到最高位排列。第四行一个整数 type\mathrm{type}。

  • type=0\mathrm{type}=0 时,第五行一个整数 kk,表示正确下标。
  • type=1\mathrm{type}=1 时,第五行一个整数 ll,第六行有 mm 个以空格分隔的 00 或 11,从最低位到最高位表示花花算出的 Mk 2lM_{k\,2^l}。

输出格式

输出一行恰有 mm 个字符的二进制串,表示正确的 MkM_k。从最低位到最高位排列,字符之间没有空格。

样例 #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。当前归档缺少这对文件。

数据范围

原赛测试点 mm 上限 kk 上限 ll type\mathrm{type} xx 为“好的”
1 1010 10910^9 不适用 0 是
2 l≤10l\le10 1
3–5 100100 不适用 0
6 10510^5 l=1l=1 1
7–9 10910^9 l≤10l\le10
10–12 10001000 101810^{18}
13–14 20002000 10910^9 不适用 0
15–16 500000500000 10610^6 否
17–20 10000001000000