#P3582. 存不下
存不下
存不下
题目描述
I never said “640K should be enough for anybody!” — Bill Gates
阿米巴是小强的好朋友。他经常和小强通过即时通讯工具聊天。但是,小强还是喜欢和阿米巴面对面的在一起的感觉,于是他想说服阿米巴放弃即时通讯工具。小强提出的一个理由是,别人可能偷看到他们两个人之间的相互说的“那些话”从而造出“大新闻”。
阿米巴认为他们可以通过加密聊天来解决这个问题。小强和阿米巴都知道,只有一次一密这种真正安全的加密算法才能保护住他们的信息。这种加密方法虽然很安全,但是需要在事前约定很长的一个随机串。
于是,小强又提出,他的 u 盘太小,根本存不下太多东西,一次无法从阿米巴那里拷贝足够长的随机串。为了减少事前约定的串的长度,阿米巴提出了一个“随机倍增器”。这个“随机倍增器”可以将一个 位的随机串变成一个 位的看起来也很随机的串。
具体的,对于一个长度为 的 串,选取参数 ,,阿米巴用下面的方法把它变成一个长度为 的串:
初始令 ,。从左到右处理输入的每一位 ,依次执行下列操作。各行使用此前已经更新的值。
$$\begin{aligned} s &\gets \bigl(\operatorname{RotL}((3432918353s+c)\bmod 2^{32},32)\cdot461845907\bigr)\bmod 2^{32},\\ h &\gets h\oplus (s\bmod 2^m)\oplus x_i,\\ h &\gets \operatorname{RotL}(h,m),\\ h &\gets (5h+3864292196)\bmod 2^m. \end{aligned}$$其中 表示按位异或,模运算取非负余数。 表示将 的 位二进制表示循环左移一位:最高位移到最低位,其余各位上移。例如 ,即将二进制的 变成 。
每轮更新后,将此时 的最高位和次高位依次追加到输出串。例如 时,追加两位 。
小强从这个算法的常数中一下就看出了这个算法改造自著名的 murmurHash3。不过,小强认为阿米巴连 NOIP 都没有考过,他改造出来的算法一定是有缺陷的。阿米巴偏偏不信这点。
为了向阿米巴说明这个算法的“随机性”不是特别强,小强想精心构造一个输入串,使得输出串中 的个数特别多。我们知道,如果这个算法真的很随机,因为输入只有 位,所以输出中应该是不会有太多的 的。曾经获得过 NOIP 普及组二等奖的小强还是有一定的算法能力的,他很快就想出了一个构造的算法。但是,问题在于小强没有带笔记本,他只能用自己的手机上的浏览器运行 javascript 来进行计算。但是手机上的内存非常紧张,需要用的数组根本存不下!
为了小强和阿米巴在一起的美好时光,你要利用非常紧缺的内存来完成输入串的构造。
输入格式
一行三个整数 。
输出格式
第一行一个整数,表示输出串中 的个数的最小值。
第二行输出一个恰含 个字符的二进制串,中间没有空格。该串必须达到第一行给出的最小值;若有多解,输出任意一个。
样例
3 3 5
0
101
数据规模与约定
对于 的数据,,,,。