UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3557. [Ctsc2014]随机数

Statistics 下载数据

Description

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是,有计算机生成的随机数序列并非真正的随机数,
而是由一定法则生成的伪随机数。 
某一天,露露了解了一种生成随机数的方法,成为Mersenne twister。给定初始参数m∈Z+,x∈Z+∩[0,2m)和初值M0∈Z+∩[0,2m),
它通过下列递推式构造伪随机数列{Mn}: 
 其中XOR是二进制异或运算(C/C++中的^运算)。而参数x的选取若使得该数列在长度趋于无穷时,近似等概率地在Z+∩(0,2m)中取值,
就称x为好的。例如,在m>1时x=0就显然不是好的。 
在露露向伙伴们介绍了Mersenne twister之后,花花想用这一些经典的随机性测试来检验它的随机性强度。为此,花花使用计算机计算
了一些Mk。 
但细心的萱萱注意到,花花在某次使用二进制输入k时,在末尾多输入了l个0,。她正想告诉花花这个疏忽,然而花花已经计算并记录了
错误的Mk而没有记录k的值。虽然这其实不是什么致命的问题,但是在萱萱告诉花花她这个疏漏时,作为完美主义者的花花还是恳求萱萱
帮她修正Mk的值。萱萱便把这个任务交给了她的AI——你。 

Input

第一行包含一个正整数m, 
第二行为二进制表示的x(共m个数,从低位到高位排列) 
第三行为二进制表示的M0(排列方式同x), 
第四行包含一个整数type。 
接下来分为两种可能的情况: 
1.type=0(萱萱记下了花花的输入):则第五行包含一个整数,表示萱萱记下来的正确的k值。 
2.type=1(萱萱未能记下花花的输入):则第五行为l,第六行输入花花计算出错误的二进制表示的Mk。 

Output

仅一行,为m位的01串,表示你求得的正确Mk(同样要求从低位到高位)。 

Sample Input

10
1 1 1 0 0 1 1 1 0 0
1 1 1 0 0 0 0 0 1 1
0
100

Sample Output

0101111001

Hint

 M<=1000000  K<=10^6

Source