18050번 - Henry Porter and the Palindromic Radius 다국어

A young wizard, Henry Porter, has just received sad news – the eldest of his family, uncle Markus Radius Palindromus Black, passed away. Uncle Markus had a reputation of being a quite eccentric person, using complicated binary magic, and was also known to be very, very rich.

Black’s will states that Henry should inherit his mysterious chamber of treasures. To enter and claim it, however, the young wizard must say the right password H, which is a word of length n, consisting of characters 0 and 1. Uncle Markus did not tell Henry the password – it certainly wouldn’t be his style. Instead, he computed, for every x = 1, 2, . . . , n, the palindromic radius p_x – the largest possible integer such that the word H[x − p_x .. x + p_x] of length 2p_x + 1 centered at H[x] exists and is a palindrome. Henry then only received the values p₁, . . . , p_n. For example, if the password was 10111010, Henry would get the sequence (0, 1, 0, 3, 0, 1, 1, 0).

Henry would prefer Uncle Markus not to test his algorithmic skills while being dead, but, well, there is no one to complain. And he has good friends who can help him! Given the sequence left by Markus in his will, determine all possible passwords that correspond to it. As the will is battered and stained, it might even happen that there is no solution at all.

The first line of input contains the number of test cases z (1 ≤ z ≤ 200 000). The test cases follow, each one in the following format:

A test case consists of two lines. The first line contains a single integer n – the length of both the password and Black’s sequence (2 ≤ n ≤ 1 000 000). The second line contains n integers p₁, p₂, . . . , p_n (0 ≤ p_i ≤ n) – the palindromic radii for all the characters in the password.

The sum of n values over all test cases does not exceed 5 · 10⁷.

For every test case, output first the number k of possible passwords. If k > 0, output in the next k lines all the solutions as {0,1}-sequences. The sequences must be given in lexicographic order.

You may assume that k does not exceed 100.