#P3582. 存不下

    ID: 2783 传统题 4000ms 8MiB 尝试: 11 已通过: 5 难度: 7 上传者: 标签>难度分类提高+/省选-动态规划线性 DP滚动数组枚举与搜索路径恢复数论模逆元构造与建模逆向还原操作模拟与实现技巧位压缩存储CF2300By佚名提供

存不下

存不下

题目描述

I never said “640K should be enough for anybody!” — Bill Gates

阿米巴是小强的好朋友。他经常和小强通过即时通讯工具聊天。但是,小强还是喜欢和阿米巴面对面的在一起的感觉,于是他想说服阿米巴放弃即时通讯工具。小强提出的一个理由是,别人可能偷看到他们两个人之间的相互说的“那些话”从而造出“大新闻”。

阿米巴认为他们可以通过加密聊天来解决这个问题。小强和阿米巴都知道,只有一次一密这种真正安全的加密算法才能保护住他们的信息。这种加密方法虽然很安全,但是需要在事前约定很长的一个随机串。

于是,小强又提出,他的 u 盘太小,根本存不下太多东西,一次无法从阿米巴那里拷贝足够长的随机串。为了减少事前约定的串的长度,阿米巴提出了一个“随机倍增器”。这个“随机倍增器”可以将一个 nn 位的随机串变成一个 2×n2\times n 位的看起来也很随机的串。

具体的,对于一个长度为 nn 的 0101 串,选取参数 mm,cc,阿米巴用下面的方法把它变成一个长度为 2n2n 的串:

初始令 h=1371 mod 2mh=1371\bmod 2^m,s=0s=0。从左到右处理输入的每一位 xix_i,依次执行下列操作。各行使用此前已经更新的值。

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

其中 ⊕\oplus 表示按位异或,模运算取非负余数。RotL⁡(a,b)\operatorname{RotL}(a,b) 表示将 aa 的 bb 位二进制表示循环左移一位:最高位移到最低位,其余各位上移。例如 RotL⁡(13,4)=11\operatorname{RotL}(13,4)=11,即将二进制的 11011101 变成 10111011。

每轮更新后,将此时 hh 的最高位和次高位依次追加到输出串。例如 m=4,h=13m=4,h=13 时,追加两位 1111。

小强从这个算法的常数中一下就看出了这个算法改造自著名的 murmurHash3。不过,小强认为阿米巴连 NOIP 都没有考过,他改造出来的算法一定是有缺陷的。阿米巴偏偏不信这点。

为了向阿米巴说明这个算法的“随机性”不是特别强,小强想精心构造一个输入串,使得输出串中 00 的个数特别多。我们知道,如果这个算法真的很随机,因为输入只有 nn 位,所以输出中应该是不会有太多的 00 的。曾经获得过 NOIP 普及组二等奖的小强还是有一定的算法能力的,他很快就想出了一个构造的算法。但是,问题在于小强没有带笔记本,他只能用自己的手机上的浏览器运行 javascript 来进行计算。但是手机上的内存非常紧张,需要用的数组根本存不下!

为了小强和阿米巴在一起的美好时光,你要利用非常紧缺的内存来完成输入串的构造。

输入格式

一行三个整数 n,m,cn,m,c。

输出格式

第一行一个整数,表示输出串中 11 的个数的最小值。

第二行输出一个恰含 nn 个字符的二进制串,中间没有空格。该串必须达到第一行给出的最小值;若有多解,输出任意一个。

样例

3 3 5
0
101

数据规模与约定

对于 100%100\% 的数据,1≤n≤5×1031\le n\le 5\times 10^3,3≤m≤203\le m\le 20,n×2m≤5×107n\times 2^m\le 5\times 10^7,0≤c<2310\le c<2^{31}。