BZOJ-3557. [Ctsc2014]随机数

这是 CTSC2014 一道陈老师的可怕题目!

露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是,由计算机生成的随机数序列并非真正的随机数,而是由一定法则生成的伪随机数。

某一天,露露了解了一种生成随机数的方法,称为 Mersenne twister。给定初始参数 m \in \mathbb Z^+x \in \mathbb Z \cap [0, 2^m) 和初值 M_0 \in \mathbb Z \cap [0, 2^m),它通过下列递推式构造伪随机数列 {M_n}

 \begin{equation*} M_n = \left \{ \begin{aligned} &2M_{n-1}& ~2M_{n-1} < 2^m \\ (2M_{n-1} &-2^m) \oplus x & ~2M_{n-1} \geq 2^m \\ \end{aligned} \right. \end{equation*}

其中 \oplus 是二进制异或运算(C/C++ 中的 ^ 运算)。而参数 x 的选取若使得该数列在长度趋于无穷时,近似等概率地在 \mathbb Z \cap (0, 2^m) 中取值,就称 x 是好的。例如,在 m > 1x=0 就显然不是好的。

在露露向伙伴介绍了 Mersenne twister 之后,花花想用一些经典的随机性测试来检验它的随机性强度。为此,花花使用计算机计算了一些 M_k

但细心的萱萱注意到,花花在某次使用二进制输入 k 时,在末尾多输入了 l0。她正想告诉花花这个疏忽,然而花花已经计算并记录了错误的 M_k 值而没有记录 k 的值。虽然这其实不是什么致命的问题,但是在萱萱告诉花花她的这个疏漏时,作为完美主义者的花花还是恳求萱萱帮她修正 M_k 的值。萱萱便把这个任务交给了他的 AI ——你!

【输入格式】

输入文件 random.in 的第一行包含一个正整数 m,第二行为二进制表示的 x(共 m 个数,从低位到高位排列),第三行为二进制表示的 M_0(排列方式同 x),第四行包含一个整数 type

接下来分为两种可能的情况:

  1. type = 0(萱萱记下了花花的输入):则第五行包含一个整数,表示萱萱记下来的正确的 k 值。
  2. type = 1(萱萱未能记下花花的输入):则第五行为 l,第六行输入花花计算出错误的二进制表示的 M_k

【输出格式】

输出文件 random.out 仅一行,为一个 m 位的 01 串,表示你求得的正确的 M_k(同样要求从低位到高位排列)

【数据范围】

对于 type = 0 的部分,m, k \leq 10^6

对于 type = 1 的部分,m \leq 10^3, k \leq 10^{18}, l \leq 10x 是“好的”

每个数据点时限 20s,并且开启编译器优化

(more…)

Read More