P16120 [USTCPC 2026] Hamming Dominance

**Please note that this problem has non-standard time and memory limits!** **Due to performance differences among judge machines, the time limit has been adjusted to 2.5 s.** It is another sunny afternoon! Kruskal-chan lies on the desk, staring at this problem in a daze. “Wuwu... binary strings again... cyclic isomorphism again...” A classmate leans over: “Kruskal-chan is still struggling with this problem?” “I-I’m not struggling at all! I’m just thinking about life!” Kruskal-chan pouts, and the pen in her hand spins in circles unconsciously. But since you have already picked it up, let’s try to solve it!

A binary string $S$ of length $n$ initially has all bits set to zero. You are given $n$ operations. In each operation, you first flip one bit of $S$, and then output the number of ordered pairs of binary strings $(A, B)$ that satisfy the following two conditions: - Both $A$ and $B$ are cyclically isomorphic to $S$. - For every prefix of $A$, its Hamming weight is not less than the Hamming weight of the prefix of $B$ of the same length. Two strings are called **cyclically isomorphic** if and only if one of them can be transformed into the other by performing several left-rotation operations. Here, a “left rotation” means moving the first character of the string to the end. For example, $\texttt{abc}$ becomes $\texttt{bca}$ after one left rotation, so they are cyclically isomorphic, but they are not cyclically isomorphic to $\texttt{cba}$. The **Hamming weight** of a binary string is defined as the number of $\texttt{1}$s in it.

**This problem contains multiple test cases.** The first line contains an integer $T$ ($1\le T\le 2000$), indicating the number of test cases. For each test case, the first line contains an integer $n$ ($1\le n\le 2000$), denoting the length of the binary string. The next line contains $n$ integers, where the $i$-th integer denotes the index of the bit flipped in the $i$-th operation. Indices start from $1$. It is guaranteed that $\sum n\le 2000$.

Output $T$ lines. Each line contains $n$ integers, representing the number of valid ordered pairs after each flip.

In the second sample, after the second operation, $S$ becomes $\texttt{110}$. At this time, there are $6$ valid pairs $(A, B)$, which are: - $A=\texttt{110},B\in\{\texttt{110},\texttt{101},\texttt{011}\}$ - $A=\texttt{101},B\in\{\texttt{101},\texttt{011}\}$ - $A=B=\texttt{011}$ Translated by ChatGPT 5