UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3614. [Heoi2014]逻辑翻译

Statistics 下载数据

Description

在人类的神经系统中,每个信号都可以用?1或+1来表示。这些信号组合起来最后形成 了喜怒哀乐,酸甜苦辣,红黄绿蓝等各种各样的复杂信息。纳米探测科技的突破让生物学家 可以测量大脑中特定区域的完整逻辑功能。然而超大数据的处理一直是令 H 教授头疼的问 题。
 假设一个逻辑单元接受N个信号输入,并产生一个代表某种意义的实数值r。那么总共 可能的情况有2^N种。
通过长时间的累积测量, H 教授可以准确地获得输入信号与r的关系表:
 f:{-1,1}N →R  然而进一步研究发现,神经元的运算方式可以被建模为人们熟知的多项式。由于一个输 入
信号值的平方一定为1,所以我们可以用不含幂的2^N项的多项式来唯一表示任何一个逻辑f。 
 例如
 x1 = +1; x2 = +1   x1 = +1; x2 = -1  x1 = -1; x2 = +1 x1 = -1; x2 = -1
        0                   1                2                3  
可以写成 f(x1,x2) = 1.5 - 0.5x2 - x1 研究一个逻辑单元的多项式形式对了解大脑工作十分有意义,于是
小 M 决定帮 H 教授 把测量出的逻辑关系表全部转换成多项式的形式。这么简单的工作一定难不倒编程能手
小M 的吧? 

Input

第一行是n (1 ≤ n ≤ 20),接下来共2^n行,每一行是一组逻辑输入和一个对应值,代表 x1 …xn的符号

以及对应的r。详见样例。数据保证所有逻辑值的绝对值不超过100,且不包 含超过 2 位小数。保证所有逻
辑的输入串都互不相同。 

Output

最多2^N行,代表多项式每一项的系数,如果答案为整数,输出整数形式。

否则输出最简 分数形式。如果系数恰好为 0,则省略整行。
变量和系数用空格隔开,常数项不用加空格。 
顺序按多项式的字典序:
常数项优先;
没有常数项时,最小x下标更小的项优先
当两项含有相同最小下标时,按除掉最小下标x以后,
以同样规则递归比较。
 例: 1,x1,x1x2,x1x2x3,x1x3,x2,x2x3,x3 详见样例。 

Sample Input

#1

2
++ 0
+- 1
-+ 2
-- 3


#2

3
--- -1.0
-++ -1.0
+-+ -1.0
++- -1.0
--+ 1.0
-+- 1.0
+-- 1.0
+++ 1.0

Sample Output

#1

3/2
-1 x1
-1/2 x2

#2

1 x1x2x3

Hint

 对于 100%的数据, 1 ≤N≤ 20, |r| ≤ 100, 100r∈ Z. 


请注意输入输出的效率。 

Source

鸣谢佚名上传