#PQJ1639x7592. QOJ 1639_7592
QOJ 1639_7592
IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 随机数 随机数 【问题描述】 露露、花花和萱萱最近对计算机中的随机数产生了兴趣。为大家所熟知的是, 由计算机生成的随机数序列并非真正的随机数,而是由一定法则生成的伪随机数。 某一天,露露了解了一种生成随机数的方法,称为Mersenne twister。给定 初始参数𝑚∈ℤ+,𝑥∈ ℤ∩[0,2m)和初值𝑀0 ∈ℤ∩[0,2m),它通过下列递推式构 造伪随机数列{𝑀𝑛}: 2𝑀𝑛−1 < 2𝑚 2𝑀𝑛−1 2𝑀𝑛−1 ≥2𝑚 𝑀𝑛= { (2𝑀𝑛−1 −2𝑚) xor 𝑥 其中xor是二进制异或运算(C/C++中的^运算)。而参数𝑥的选取若使得该数 列在长度趋于无穷时,近似等概率地在ℤ∩(0,2m)中取值,就称𝑥为好的。 例如, 在𝑚> 1时𝑥= 0就显然不是好的。 在露露向伙伴们介绍了Mersenne twister 之后,花花想用一些经典的随机性 测试来检验它的随机性强度。为此,花花使用计算机计算了一些𝑀𝑘。 但细心的萱萱注意到,花花在某次使用二进制输入𝑘时,在末尾多输入了𝑙个 0。她正想告诉花花这个疏忽,然而花花已经计算并记录了错误的𝑀𝑘值而没有记 录𝑘的值。虽然这其实不是什么致命的问题,但是在萱萱告诉花花她的这个疏漏 时,作为完美主义者的花花还是恳求萱萱帮他修正𝑀𝑘的值。萱萱便把这个任务 交给了她的AI——你。 【输入格式】 输入文件random.in 的第一行包含一个正整数𝑚,第二行为二进制表示的𝑥 (共𝑚个数,从低位到高位排列),第三行为二进制表示的𝑀0(排列方式同𝑥), 第四行包含一个整数𝑡𝑦𝑝𝑒。 接下来分为两种可能的情况:
- 𝑡𝑦𝑝𝑒= 0(萱萱记下了花花的输入):则第五行包含一个整数,表示萱萱 记下来的正确的𝑘值。
- 𝑡𝑦𝑝𝑒= 1(萱萱未能记下花花的输入):则第五行为𝑙,第六行输入花花 计算出错误的二进制表示的𝑀𝑘。 【输出格式】 输出文件random.out 仅一行,为一个𝑚位的01 串,表示你求得的正确的𝑀𝑘 (同样要求从低位到高位排列)。 【样例输入1】 10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 第7 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 随机数 100 【样例输出1】 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 【样例输出2】 0101111001 【样例输入输出3】 见选手目录下的random/random.in 与random/random.ans。 【数据规模和约定】 测试点编 𝑥是否为“好 𝑚 𝑙 𝑡𝑦𝑝𝑒 𝑘 号 的” ≤109 1 N/A 0 是 ≤10 ≤109 2 1 是 ≤10 ≤10 ≤109 3 N/A 0 是 ≤100 ≤109 4 N/A 0 是 ≤100 ≤109 5 N/A 0 是 ≤100 6 ≤105 1 是 ≤100 = 1 ≤109 7 1 是 ≤100 ≤10 ≤109 8 1 是 ≤100 ≤10 ≤109 9 1 是 ≤100 ≤10 ≤1018 10 1 是 ≤1000 ≤10 ≤1018 11 1 是 ≤1000 ≤10 ≤1018 12 1 是 ≤1000 ≤10 ≤109 13 N/A 0 是 ≤2000 第8 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 随机数 ≤109 14 N/A 0 是 ≤2000 ≤106 15 N/A 0 否 ≤500000 ≤106 16 N/A 0 否 ≤500000 ≤106 17 N/A 0 否 ≤1000000 ≤106 18 N/A 0 否 ≤1000000 ≤106 19 N/A 0 否 ≤1000000 ≤106 20 N/A 0 否 ≤1000000 第9 页 共9 页