P4106 [HEOI2014] Logic Translation

In the human nervous system, each signal can be represented by $−1$ or $+1$. These signals combine to eventually form complex information such as joy, anger, sorrow, and happiness; sour, sweet, bitter, and spicy; red, yellow, green, and blue. Breakthroughs in nano-probing technology have enabled biologists to measure the complete logical function of specific regions of the brain. However, processing ultra-large data has always been a headache for Professor H. Suppose a logical unit accepts $N$ signal inputs and produces a real value $r$ representing some meaning. Then there are $2^N$ possible cases in total. Through long-term cumulative measurements, Professor H can accurately obtain the mapping between input signals and $r$: $$f :\{-1,1\}^N \to \mathbb{R} $$ Further research has found that the neuron’s computation can be modeled as a well-known polynomial. Since the square of an input signal value is always $1$, we can uniquely represent any logic $f$ by a polynomial without powers consisting of $2^N$ terms. For example x1=+1; x2=+1 -> 0 x1=+1; x2=-1 -> 1 x1=-1; x2=+1 -> 2 x1=-1; x2=-1 -> 3 can be written as $$f(x_1,x_2)=1.5-0.5x_2-x_1$$ Studying the polynomial form of a logical unit is very meaningful for understanding how the brain works, so Xiao M decided to help Professor H convert all measured logic tables into polynomial form. Such a simple task should be no problem for the coding ace Xiao M, right?

The first line is $N$ ($1\le N \le20$). Then there are $2^N$ lines. Each line contains one set of logical inputs and one corresponding value, representing the signs of $x_1...x_N$ and the corresponding $r$. See the sample. The testdata guarantees that the absolute value of every logical value does not exceed $100$, and it contains no more than $2$ decimal places. All logical input strings are guaranteed to be pairwise distinct.

Up to $2^N$ lines, representing the coefficient of each term in the polynomial. If a coefficient is an integer, output it in integer form; otherwise, output it as an irreducible fraction. If a coefficient is exactly $0$, omit the entire line. Separate variables and the coefficient with a space; the constant term should not have a space. Order by the polynomial’s lexicographic order: 1. The constant term comes first. 2. Among non-constant terms, the term with the smaller smallest $x$ index comes first. 3. If two terms share the same smallest index, remove that smallest-indexed $x$ and compare recursively using the same rule. Example: $1$, $x1$, $x1x2$, $x1x2x3$, $x1x3$, $x2$, $x2x3$, $x3$. See the sample.

This problem has $10$ testdata. For the $1$st testdata, $N\le3$; for the $2$nd testdata, $N\le8$; for the $3$rd and $4$th testdata, $N\le11$; for the $5$th and $6$th testdata, the answer polynomial has only one nonzero term, as in Sample #2; for the $7$th and $8$th testdata, the answer polynomial has at most $5$ nonzero terms. For $100\%$ of the testdata, $1 \le N \le 20, |r| \le 100, 100r\in \mathbb{Z}$. Friendly reminder Please pay attention to input and output efficiency. Translated by ChatGPT 5