题目描述
在人类的神经系统中，每个信号都可以用?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 的吧？
题解
这题意思是给多项式的点值表达，让你把系数求出来。
关键是它的多项式很鬼畜，有x1,x2,还有x1,x2让人感觉很烦。
对于这么一个多项式a1+a2x1+a3x2+a4x1x2,我们把x1提出来，式子就变成了x1(a2+a4x2)+a1+a3x2。
把x1去掉，加号两边的东西是不是长得很像？
我们令两个点值表达只有x1不同，x1=-1时值为a，x1=1时值为b，那么左边那一坨就是(b-a)/2,右边那一坨就是(a+b)/2。
于是我们成功的把问题规模减小了一半。
其实这个思路和FFT几乎一模一样。
然后这道题的输出很诡异，要求字典序输出，可以用dfs实现。
还有我的操作有些鬼畜，导致最后分治出的序列和答案序列不一样，所以我又nlogn模拟了一遍把答案顺序排好。。
代码
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=(<<)+;
double x;
int n,top,p[N];
char s[N];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
ll gcd(ll x,ll y){if(x<)x=-x;if(y<)y=-y;return y?gcd(y,x%y):x;}
struct fs{
ll x,y;
fs operator +(const fs &b)const{
ll xx=x*b.y+y*b.x,yy=y*b.y*;
ll g=gcd(yy,xx);
xx/=g;yy/=g;
return fs{xx,yy};
}
fs operator -(const fs &b)const{
ll xx=x*b.y-y*b.x,yy=y*b.y*;
ll g=gcd(yy,xx);
xx/=g;yy/=g;
return fs{xx,yy};
}
}dp[N];
void dfs(int num,int x){
if(num>n)return;
p[++top]=x|(<<num-);
dfs(num+,x|(<<num-));dfs(num+,x);
}
int main(){
n=rd();
for(int i=;i<(<<n);++i){
int o=;scanf("%s%lf",s+,&x);
for(int j=;j<=n;++j){
o<<=;o|=(s[j]=='+'?:);
}
if(x>)dp[o].x=(int)(x*+0.1);//因为要向0取整，所以要判断正负
else dp[o].x=(int)(x*-0.1);
dp[o].y=;
ll g=gcd(dp[o].x,dp[o].y);
dp[o].x/=g;dp[o].y/=g;
}
for(int i=(<<n-);i>=;i>>=)
for(int j=;j<(<<n);j+=(i<<))
for(int k=;k<i;++k){
fs x=dp[k+j],y=dp[k+i+j];
dp[k+j]=y-x;dp[k+i+j]=x+y;
}
for(int i=;i<(<<n);++i){
int x=i,l=,r=(<<n)-;
while(l!=r){
int mid=(l+r)>>;
if(x&)r=mid;else l=mid+;x>>=;
}
if(l<i)swap(dp[l],dp[i]);
}
dfs(,);
for(int i=;i<(<<n);++i){
int x=p[i];
if(!dp[x].x)continue;
if(dp[x].y<)dp[x].y=-dp[x].y,dp[x].x=-dp[x].x;
if(dp[x].y!=)
printf("%lld/%lld ",dp[x].x,dp[x].y);
else printf("%lld ",dp[x].x);
for(int j=;j<=n;++j)if(x&(<<j-))printf("x%d",j);
printf("\n");
}
return ;
}