[HEOI2014] 逻辑翻译
题目描述
在人类的神经系统中,每个信号都可以用−1或+1来表示。这些信号组合起来最后形成 了喜怒哀乐,酸甜苦辣,红黄绿蓝等各种各样的复杂信息。纳米探测科技的突破让生物学家 可以测量大脑中特定区域的完整逻辑功能。然而超大数据的处理一直是令 H 教授头疼的问 题。
假设一个逻辑单元接受N个信号输入,并产生一个代表某种意义的实数值r。那么总共可能的 情况有2N种。通过 长时间的累积测量, H 教授可以准确地获得输入信号与r的关系表:
$$f :{-1,1}N \to \mathbb{R} $$
然而进一步研究发现,神经元的运算方式可以被建模为人们熟知的多项式。由于一个输 入信号值的平方一定为1,所以我们可以用不含幂的2N项的多项式来唯一表示任何一个逻辑 f。
例如
$x_1=+1; x_2=+1 \to 0$
$x_1=+1; x_2=-1 \to 1$
$x_1=-1; x_2=+1 \to 2$
$x_1=-1; x_2=-1 \to 3$
可以 写成
$$f(x_1,x_2)=1.5-0.5x_2-x_1$$
研究一个逻辑单元的多项式形式对了解大脑工作十分有意义,于是小 M 决定帮 H 教授 把测量出的逻辑关系表全部转换成多项式的形式。这么简单的工作一定难不倒编程能手小M 的吧?
输入输出格式
输入格式
第一行是N (1≤N≤20),接下来共2N行,每一行是一组逻辑输入和一个对应值,代表 x\_1...x\_N的符号以及对应的r。详见样例。数据保证所有逻辑值的绝对值不超过100,且不包含超过 2 位小数。保证所有逻辑的输入串都互不相同。
输出格式
最多$2^N$行,代表多项式每一项的系数,如果答案为整数,输出整数形式。否则输出最 简分数形式。如果系数恰好为 0,则省略整行。变量和系数用空格隔开,常数项不用加空格。
顺序按多项式的字典序:
1. 常数项优先;
2. 没有常数项时,最小x下标更小的项优先;
3. 当两项含有相同最小下标时,按除掉最小下标x以后,以同样规则递归比较。
例:1,x1,x1x2,x1x2x3,x1x3,x2,x2x3,x3 详见 样例。
输入输出样例
输入样例 #1
2
++ 0
+- 1
-+ 2
-- 3
输出样例 #1
3/2
-1 x1
-1/2 x2
输入样例 #2
3
--- -1.0
-++ -1.0
+-+ -1.0
++- -1.0
--+ 1.0
-+- 1.0
+-- 1.0
+++ 1.0
输出样例 #2
1 x1x2x3
说明
本题共有 10 个测试数据。
对于第 1 个数据, N≤3;
对于第 2 个数据, N≤8;
对于第 3,4 个数据,N≤11;
对于第 5,6 个数据, 答案多项式中只有一个非零项,如样例#2。
对于第 7,8 个数据, 答案多项式中最多有 5 个非零项。
对于 100%的数据, $1 \le N \le 20,|r| \le 100, 100r\in \mathbb{Z} $
友情提示
请注意输入输出的效率。