Misheard Binary
Time limit2sMemory limit128 MB
Count distinct binary strings obtainable by shifting each bit of an N-bit number at most D positions, then output the K-th smallest such string.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Combinatorics, Prefix sum, Greedy
- Solved
- No attempts yet
Problem
Minsik often mishears what other people say. When someone says an N-bit binary number, Minsik hears a slightly different number. The i-th bit of the spoken number ends up at the j-th position of the number Minsik hears, and it always holds that |j - i| ≤ D. Each position receives exactly one original bit, so the number Minsik hears is a rearrangement (permutation) of the spoken number in which every bit moves at most D places from its original position.
For example, if the spoken number is 0110 and D = 1, the numbers Minsik can hear are 0101, 0110, 1001, and 1010 — four in total.
Given the spoken binary number and the integers D and K, find how many distinct binary numbers Minsik can hear, and the K-th smallest among those candidates.
Input
The first line contains the number of bits N (1 ≤ N ≤ 2,000), the integer D (0 ≤ D < N), and the integer K (1 ≤ K ≤ 100,000,000), separated by spaces.
The second line contains the spoken N-bit binary number.
Output
On the first line, print the number of distinct binary numbers Minsik can hear, modulo 100,000,000.
On the second line, print the K-th smallest candidate as an N-bit binary number (keeping any leading zeros).