#P1581. [Usaco2009 Hol]Transmission Delay 传输谍延时

    ID: 595 传统题 1000ms 256MiB 尝试: 210 已通过: 79 难度: 6 上传者: 标签>CF2000提高局部交换消除逆序计数 DP线性 DP状态维度消除序列构造Gold

[Usaco2009 Hol]Transmission Delay 传输谍延时

题目描述

约翰在屋顶上唱歌,以此来与奶牛们交流。但是奶牛们的听力很奇怪,她们只能听到约翰的歌声变成 00 和 11 构成的信息串时的样子。 约翰的声音里有 nn 个 00 或 11,奶牛听到的也是 nn 个,而且 00 和 11 的数量不会变化,但是一部分 00 或 11 可能偏离原来的位置,这就是约翰的歌声在传输时发生的"传输延迟"现象。00 或 11 的偏离距离不会超过 dd,也就是说某一个码的原本位置和现在的位置之差的绝对值不大于 dd。

比如,对于 01100110,d=1d=1,传输延迟发生后可能出现 01010101,01100110,10011001,10101010 这四种串。

给出约翰歌声的 0101 串形式和一个整数kk,请计算传输延迟发生后一共有多少种可能的 0101 串,以及其中按字典序从小到大排列后的第 kk 个的串是什么。

输入格式

  • 第 11 行:33 个整数:n,d,kn,d,k。
  • 第 22 行:11 个 nn 位的二进制数字,代表信息串。

输出格式

  • 第 11 行:11 个整数:收到整数的种数(对 10810^8 取模)
  • 第 22 行:11 个整数:11 个 nn 位的二进制数字,代表按字典序从小到大排列后的第 kk 个的串。
4 1 3
0110
4
1001

数据规模与约定

对于 100%100\% 的数据,1≤n≤20001\le n \le 2000,0≤d<n 0 \le d < n,1≤k≤1081 \le k \le 10^8。

保证 kk 不超过可以收到的不同信息串数量。