T739397 [CFCOI] 多边形

$\textrm{polygon.cpp, 1.5 s, \textcolor{red}{64} MiB}$ **注意 $k$ 的范围。**

给定 $n$，请问是否可以构造若干个多边形使得： 1. 这些多边形可以拼成**长为 $n$，宽为 $1$ 的长方形**。 2. 这些多边形可以拼成**正方形**。 3. 在拼接上述的两个矩形的时候，所有多边形的顶点均在格点上，且都至少有一条边平行于坐标轴。 由于这个问题太水了，你需要对所有 $1 \le n \le k$ 求解。

仅一行，一个整数 $k$。

由于本题输出量过大，按照以下方式输出： 设 $n=i$ 时的答案为 $f_i$。若可以构造则 $f_i=1$，否则 $f_i=0$。 然后，构造一个长度为 $\lfloor k/6 \rfloor$ 的数列 $\{g_{\lfloor k/6 \rfloor}\}$。其中 $g_i=(\overline{f_{6i-5}f_{6i-4}f_{6i-3}f_{6i-2}f_{6i-1}f_{6i}})_2$。 最后，你需要将 $g$ 变换为字符串 $s$，并输出字符串 $s$。具体地，$g_i$ 与 $s_i$ 的关系如下表。 | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | $s_i$ | $g_i$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $\texttt{A}$ | $0$ | $\texttt{I}$ | $8$ | $\texttt{Q}$ | $16$ | $\texttt{Y}$ | $24$ | $\texttt{g}$ | $32$ | $\texttt{o}$ | $40$ | $\texttt{w}$ | $48$ | $\texttt{4}$ | $56$ | | $\texttt{B}$ | $1$ | $\texttt{J}$ | $9$ | $\texttt{R}$ | $17$ | $\texttt{Z}$ | $25$ | $\texttt{h}$ | $33$ | $\texttt{p}$ | $41$ | $\texttt{x}$ | $49$ | $\texttt{5}$ | $57$ | | $\texttt{C}$ | $2$ | $\texttt{K}$ | $10$ | $\texttt{S}$ | $18$ | $\texttt{a}$ | $26$ | $\texttt{i}$ | $34$ | $\texttt{q}$ | $42$ | $\texttt{y}$ | $50$ | $\texttt{6}$ | $58$ | | $\texttt{D}$ | $3$ | $\texttt{L}$ | $11$ | $\texttt{T}$ | $19$ | $\texttt{b}$ | $27$ | $\texttt{j}$ | $35$ | $\texttt{r}$ | $43$ | $\texttt{z}$ | $51$ | $\texttt{7}$ | $59$ | | $\texttt{E}$ | $4$ | $\texttt{M}$ | $12$ | $\texttt{U}$ | $20$ | $\texttt{c}$ | $28$ | $\texttt{k}$ | $36$ | $\texttt{s}$ | $44$ | $\texttt{0}$ | $52$ | $\texttt{8}$ | $60$ | | $\texttt{F}$ | $5$ | $\texttt{N}$ | $13$ | $\texttt{V}$ | $21$ | $\texttt{d}$ | $29$ | $\texttt{l}$ | $37$ | $\texttt{t}$ | $45$ | $\texttt{1}$ | $53$ | $\texttt{9}$ | $61$ | | $\texttt{G}$ | $6$ | $\texttt{O}$ | $14$ | $\texttt{W}$ | $22$ | $\texttt{e}$ | $30$ | $\texttt{m}$ | $38$ | $\texttt{u}$ | $46$ | $\texttt{2}$ | $54$ | $\texttt{+}$ | $62$ | | $\texttt{H}$ | $7$ | $\texttt{P}$ | $15$ | $\texttt{X}$ | $23$ | $\texttt{f}$ | $31$ | $\texttt{n}$ | $39$ | $\texttt{v}$ | $47$ | $\texttt{3}$ | $55$ | $\texttt{=}$ | $63$ |

#### 样例解释 $f=\{1,1,0,1,1,0\}$； $g=\{54\}$。 #### 数据范围 ::cute-table{tuack} | 测试点 | $k=$ | 分值 | |:-:|:-:|:-:| | $1$ | $6$ | $0$ | | $2$ | $12$ | $10$ | | $3$ | $5 \times 10^3$ | $20$ | | $4$ | $10^6$ | $30$ | | $5$ | $2 \times 10^8$ | $40$ |