P5890 Xiao Ou and Palindrome String Construction

Xiao Ou likes strings, especially palindromic strings that contain only the two characters `0` and `1`. Xiao Ou also likes palindromes, especially strings that have some palindromic substrings, but not too many. Xiao Ou likes construction even more, so he thinks about the following problem: Given positive integers $n$ and $k$, with $k \le n$ guaranteed, can you construct a string $S$ of length $n$ consisting only of characters `0` and `1`, such that the number of essentially different non-empty palindromic substrings of $S$ is exactly $k$? Xiao Ou is a construction newbie and cannot beat the predecessors who have already brute-forced 100,000 or even 90,000 construction problems, so he asks you to help solve this problem, and hopes that when a solution exists, you can output any valid construction. Some basic definitions about strings are given below. If you are very familiar with strings, you may skip this part. - For a string $S$ of length $n$, let $S_i$ be the $i$-th character of $S$ from left to right. - For a string $S$ of length $n$, define its substring $S[l;r]\; (1\le l\le r\le n)$ as the string formed by concatenating $S_l, S_{l+1}, \ldots, S_r$ from left to right. In particular, the empty string is also a substring of $S$. - Two substrings $S[l_1;r_1]$ and $S[l_2;r_2]$ of $S$ are called essentially different if and only if $S[l_1;r_1] \ne S[l_2;r_2]$. - For a string $S$ of length $n$, define its reverse string $S^{T}$ as the string formed by concatenating $S_n, S_{n-1}, \ldots, S_1$ from left to right. - A string $S$ is a palindrome if and only if $S = S^{T}$.

**This problem has multiple test cases**. The first line contains a positive integer $T$, representing the number of test cases. For each test case: One line contains two positive integers, representing $n$ and $k$ for this test case.

For each test case: If there is no solution, output one line with the string `No`. Otherwise, output two lines. The first line is the string `Yes`, and the next line is a `01` string of length $n$, which is your constructed solution. If there are multiple solutions, output any one.

For the first test case, the essentially different palindromic substrings are: `1`, `0`, `101`, `010`, for a total of four. ### Constraints and Notes For $20\%$ of the testdata, $n \le 15$. For another $10\%$ of the testdata, $k = n$. For another $20\%$ of the testdata, $1000 \le n \le 2000$, $k \ge \left\lfloor\dfrac{n}{2}\right\rfloor + 100$. For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le k \le n \le 2\times 10^5$. Translated by ChatGPT 5