21085번 - Output Limit Exceeded 스페셜 저지다국어

We all know that $\binom{n}{k} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdot \ldots \cdot (k-1) \cdot k}$ is an integer number for any $0 \le k \le n$. But it would be nice if we could prove it by providing a matching between factors in numerator and denominator, wouldn't it?

Let's build a bipartite graph with $k$ vertices in each part. The $i$-th vertex in the left part corresponds to factor $(n+1-i)$ from numerator and $j$-th vertex in the right part corresponds to factor $j$ from denominator. There is an edge $i$ --- $j$ if and only if $j$ divides $(n+1-i)$. The number $k$ is provable for $n$ if there is a perfect matching in this bipartite graph.

Given $n$, check if $k$ is provable for each $k$ satisfying $0 \le k \le n$.

The only line contains one integer $n$ ($0 \le n \le 10^{18}$).

Print string of length $(n+1)$ consisting of '0' and '1', $(k+1)$-th character should be '1' if and only if $k$ is provable for $n$.

What, you think this will get Output Limit Exceeded? Hmmmm... Okay. Let's compress the string.

Let $s_0 = \text{“0”}$ and $s_1 = \text{“1”}$. You can define $s_{2}, s_{3}, \ldots, s_{t}$. String $s_{i}$ should be a concatenation of several earlier defined strings. Formally, $\forall \: i \: (2 \le i \le t): s_{i} = s_{j_{1}} + s_{j_{2}} + \ldots + s_{j_{k_{i}}}$, here $1 \le k_{i}$, $\forall \: r \: (1 \le r \le k_{i}): j_{r} < i$. String $s_{t}$ should be the answer to the problem.

In the first line print one integer $t$ ($2 \le t \le 500$).

In the next $t-1$ lines print the descriptions of $s_{i}$. Each description should have a form $k_{i} \: j_{1} \: j_{2} \: \ldots \: j_{k_{i}}$, with $1 \le k_{i}$ and $0 \le j_{r} < i$.

Total length of all descriptions should not exceed $10\,000$: $\sum_{i=2}^{t} k_{i} \le 10\,000$.

We can show that for all valid tests there exists a way to construct the answer string abiding all the limitations. If there are several possible ways to do so, print any one of them. Note that you don't have to minimize $t$ or total length of all descriptions.

In the third sample: $s_2 = s_1 + s_1 = \text{"1"}+\text{"1"} = \text{"11"}$, $s_3 = s_1 + s_2 + s_0 + s_0 = \text{"1"}+\text{"11"}+\text{"0"}+\text{"0"} = \text{"11100"}$, $s_4 = s_3 + s_1 + s_2 = \text{"11100"}+\text{"1"}+\text{"11"} = \text{"11100111"}$,