#P3614. [Heoi2014]逻辑翻译

    ID: 2821 传统题 5000ms 64MiB 尝试: 177 已通过: 76 难度: 7 上传者: 标签>难度分类提高+/省选-多项式与生成函数FWT数值计算与优化有理数精确运算数论欧几里得算法枚举与搜索全子集枚举CF2200鸣谢佚名上传

[Heoi2014]逻辑翻译

[HEOI2014] 逻辑翻译

题目描述

在人类的神经系统中,每个信号都可以用−1-1 或 +1+1来表示。这些信号组合起来最后形成 了喜怒哀乐,酸甜苦辣,红黄绿蓝等各种各样的复杂信息。纳米探测科技的突破让生物学家 可以测量大脑中特定区域的完整逻辑功能。然而超大数据的处理一直是令 H 教授头疼的问 题。

假设一个逻辑单元接受 NN 个信号输入,并产生一个代表某种意义的实数 rr。那么总共可能的 情况有 2N2^N 种。通过 长时间的累积测量, H 教授可以准确地获得输入信号与 rr的关系表:

f ⁣:{−1,1}N→Rf\colon\{-1,1\}^N\to\mathbb R

然而进一步研究发现,神经元的运算方式可以被建模为人们熟知的多项式。由于一个输 入信号值的平方一定为1,所以我们可以用至多 2N2^N 项且每个变量在每一项中至多出现一次的多项式来唯一表示任何一个逻辑 f。

例如 x1=+1;x2=+1→0x_1=+1; x_2=+1 \to 0

x1=+1;x2=−1→1x_1=+1; x_2=-1 \to 1

x1=−1;x2=+1→2x_1=-1; x_2=+1 \to 2

x1=−1;x2=−1→3x_1=-1; x_2=-1 \to 3

可以 写成

f(x1,x2)=1.5−0.5x2−x1f(x_1,x_2)=1.5-0.5x_2-x_1

研究一个逻辑单元的多项式形式对了解大脑工作十分有意义,于是小 M 决定帮 H 教授 把测量出的逻辑关系表全部转换成多项式的形式。这么简单的工作一定难不倒编程能手小M 的吧?

输入格式

第一行一个整数 NN。接下来 2N2^N 行,每行给出一个由加号和减号组成的长度为 NN 的字符串,再给出实数 rr,分别表示 x1,…,xNx_1,\ldots,x_N 的取值以及对应的函数值。每种输入取值恰好出现一次。

输出格式

最多2N2^N行,代表多项式每一项的系数,如果答案为整数,输出整数形式。否则输出最简分数形式。如果系数恰好为 0,则省略整行。每行先输出系数。对于非常数项,在系数后输出一个空格,再按下标递增顺序连续输出该项的变量,变量之间不加空格。常数项只输出系数。

顺序按多项式的字典序:

  1. 常数项优先;
  2. 没有常数项时,最小x下标更小的项优先;
  3. 当两项含有相同最小下标时,按除掉最小下标x以后,以同样规则递归比较。

例如,N=3N=3 时,顺序为 1,x1,x1x2,x1x2x3,x1x3,x2,x2x3,x31,x_1,x_1x_2,x_1x_2x_3,x_1x_3,x_2,x_2x_3,x_3。

样例

样例 1

2
++ 0
+- 1
-+ 2
-- 3
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
1 x1x2x3

数据范围

1≤N≤201\le N\le20,∣r∣≤100|r|\le100,且 100r100r 为整数。

原题测试点 特殊限制
1 N≤3N\le3
2 N≤8N\le8
3–4 N≤11N\le11
5–6 结果只有一项非零项
7–8 结果至多有五项非零项

原题有十个测试点。请注意输入输出效率。