Fibonacci Suffix
Contest: Educational Codeforces Round 52 (Rated for Div. 2)
Difficulty rating: 2700
Tags: strings

Let's denote (yet again) the sequence of Fibonacci strings:

$$$F(0) = $$$ 0, $$$F(1) = $$$ 1, $$$F(i) = F(i - 2) + F(i - 1)$$$, where the plus sign denotes the concatenation of two strings.

Let's denote the lexicographically sorted sequence of suffixes of string $$$F(i)$$$ as $$$A(F(i))$$$. For example, $$$F(4)$$$ is 01101, and $$$A(F(4))$$$ is the following sequence: 01, 01101, 1, 101, 1101. Elements in this sequence are numbered from $$$1$$$.

Your task is to print $$$m$$$ first characters of $$$k$$$-th element of $$$A(F(n))$$$. If there are less than $$$m$$$ characters in this suffix, then output the whole suffix.

Input format:
The only line of the input contains three numbers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$, $$$1 \le k \le 10^{18}$$$) denoting the index of the Fibonacci string you have to consider, the index of the element of $$$A(F(n))$$$ and the number of characters you have to output, respectively.

It is guaranteed that $$$k$$$ does not exceed the length of $$$F(n)$$$.

Output format:
Output $$$m$$$ first characters of $$$k$$$-th element of $$$A(F(n))$$$, or the whole element if its length is less than $$$m$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
4 5 3

Example output:
110

Example input:
4 3 3

Example output:
1

Editorial:
Suppose we added all the suffixes of $$$F(n)$$$ into a trie. Then we can find $$$k$$$-th suffix by descending the trie, checking the sizes of subtrees to choose where to go on each iteration.
The model solution actually does that, but computes the sizes of subtrees without building the whole trie. Recall that if we insert all suffixes of a string into the trie, then the size of subtree of some vertex is equal to the number of occurences of the string denoted by this vertex in the original string.
Since in our problem the strings are recurrent, we may use prefix automaton to count the number of occurences. To calculate the number of occurences of string $$$s$$$ in $$$F(x)$$$, let's build prefix function for $$$s$$$, and an automaton $$$A_{p, c}$$$ which tells the value of prefix function, if the previous value was $$$p$$$, and we appended $$$c$$$ to the string (the same approach is used in KMP substring search algorithm). Then, let's build another automaton that will help us work with Fibonacci string: $$$F_{p, x}$$$ — what will be the value of prefix function, if we append $$$F(x)$$$ to the string? For $$$x = 0$$$ and $$$x = 1$$$, this automaton can be easily built using $$$A_{p, 0}$$$ and $$$A_{p, 1}$$$; and for $$$x > 1$$$, we may build $$$F_{p, x}$$$ using the automatons for $$$x - 2$$$ and $$$x - 1$$$. We also have to keep track of the number of occurences, that can be done with another automaton on fibonacci strings.
There is a corner case when we need to stop descending the trie; to handle it, we need to check whether some string is a suffix of $$$F(n)$$$, but that can be easily made by checking if $$$F_{0, n} = |s|$$$.
Each step in trie forces us to do up to three (depending on your implementation) queries like "count the number of occurences of some string in $$$F(n)$$$", so overall the solution works in $$$O(n m^2)$$$.