题目链接
题意分析
这道题就是上来一个多项式
[f(x_1,x_2,x_3)=a_0+a_1x_1+a_2x_2+a_3x_3+a_4x_1x_2+a_5x_1x_3+a_6x_2x_3+a_7x_1x_2x_3
]
然后通过对于(x_1,x_2,x_3)不同的取值对应的函数值让我们得到这个多项式的系数
首先 你可以暴力高斯消元 复杂度优美到飞起
其实对于这道题的话 如果你们有FFT或者FWT的经验的话 这道题的思路应该是比较应该是比较好想的反正本蒟蒻是没有
上述多项式转化一下
[f(x_1,x_2,x_3)=a_0+a_2x_2+a_3x_3+a_6x_2x_3+x_1(a_1+a_4x_2+a_5x_3+a_7x_2x_3)
]
然后的话 我们就可以分治了 但是对于左右应该怎么分治？
我们考虑一下 对于(x_1)存在(1)以及(-1)两种取值
那么取值不同的话就是(A)以及(B)
然后我们可以是左半部分(frac{A+B}{2}) 右半部分(frac{A-B}{2})
左半部分就是计算(x_2,x_3,x_2x_3)的系数以及常数项
右半部分就是计算(x_1,x_1x_2,x_1x_3,x_1x_2x_3)的系数
这大概就是答题的思路
然后就是这道题一些比较有意思坑人的地方
1.由于这道题的答案都是使用分数的形式输出 所以我们需要维护一个结构体进行分数运算
2.这道题的输出比较呛人 所以我们考虑直接dfs输出
3.一开始对于小数x的话 由于ta最多不超过2位小数 所以我们可以转化为分子round(100x) 分母(x) （round()函数是四舍五入的意思）
具体的实现我们还是看代码实现
CODE:
#include<bits/stdc++.h>
#define N 22
#define M 1508611
using namespace std;
char s[N];
long long gcd(long long x,long long y){return y ? gcd(y,x%y):x;}
struct Node
{//我用于维护分数的结构体
long long up,dow;//分子分母如果不使用long long的话中间结果会炸
friend Node operator +(const Node &A,const Node &B)
{
Node tmp;long long x;
tmp.up=A.up*B.dow+A.dow*B.up;
tmp.dow=A.dow*B.dow;
x=gcd((tmp.up>0 ? tmp.up:-tmp.up),(tmp.dow>0 ? tmp.dow:-tmp.dow));
if(tmp.dow<0) tmp.dow=-tmp.dow,tmp.up=-tmp.up;
return (Node){tmp.up/x,tmp.dow/x};
}
friend Node operator -(const Node &A,const Node &B)
{
Node tmp;long long x;
tmp.up=A.up*B.dow-A.dow*B.up;
tmp.dow=A.dow*B.dow;
x=gcd((tmp.up>0 ? tmp.up:-tmp.up),(tmp.dow>0 ? tmp.dow:-tmp.dow));
if(tmp.dow<0) tmp.dow=-tmp.dow,tmp.up=-tmp.up;
return (Node){tmp.up/x,tmp.dow/x};
}
friend Node operator /(const Node &A,int B)
{
Node tmp;long long x;
tmp.up=A.up;tmp.dow=A.dow*B;
x=gcd((tmp.up>0 ? tmp.up:-tmp.up),(tmp.dow>0 ? tmp.dow:-tmp.dow));
if(tmp.dow<0) tmp.dow=-tmp.dow,tmp.up=-tmp.up;
return (Node){tmp.up/x,tmp.dow/x};
}
}num[M];
int n;
bool vis[M];
void print(int now)
{
if(vis[now]||num[now].up==0) return;
//这里为了防止重复输出 我使用了一个标记数组
//同时分子为0的话 就是本身值为0 那么就不用输出了
vis[now]=1;
Node x=num[now];
if(x.dow==1) printf("%lld ",x.up);
else printf("%lld/%lld ",x.up,x.dow);
for(int i=0;i<n;++i)
if(now&(1<<i)) printf("x%d",i+1);
puts("");
}
void dfs_ans(int tox,int nowhave)
{//我们是从低位到高位递归 对应的就是1,2,3,...,n
//nowhave就是当前枚举的位
//tox就是已经枚举了的低位状态
if(nowhave==n) return;
for(int i=0;i<(1<<(n-nowhave-1));++i)
{//所以当前就是在枚举高位的状态
int cdy=(i<<(nowhave+1))|(tox)|(1<<nowhave);//高位的状态|已经枚举了的低位状态|当前位是0还是1
int wzy=(i<<(nowhave+1))|(tox);
Node tmp=num[cdy];
//这里的话我一直都不太好理解 后来才稍稍有些眉目
//我们还是考虑一下 对于题目给出的2^n个状态 其他条件分别取了x1=1以及x1=-1时对应的函数值对应着什么
num[cdy]=(tmp-num[wzy])/2;
num[wzy]=(tmp+num[wzy])/2;
//我们按照上面的做法 消掉之后
//就是等于当前这一位取0时(x2,x3,x2x3,常数项) 不同状态对应的不同函数值
//以及当前这一位取1时(x1,x1x2,x1x3,x1x2x3) 不同状态对应的不同函数值
//最后也就是相当于是axi+C 也就是a+C以及-a+C 从而得到我们要的答案
}
dfs_ans(tox,nowhave+1);
dfs_ans(tox|(1<<nowhave),nowhave+1);
//然后我们分别用取和不取对应的状态 向高位前进
}
void print_ans(int tox,int nowhave)
{
if(nowhave==n)
{//最后到了的话就是直接输出
print(tox);
return;
}
print(tox);//当前这一位没有的话自然是字典序优先级最高的 所以我们优先输出
print_ans((tox|(1<<nowhave)),nowhave+1);//然后的话就是低位先有低位优先
print_ans(tox,nowhave+1);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<(1<<n);++i)
{
int now=0;double tmp;
scanf("%s %lf",s,&tmp);
for(int j=0;j<n;++j)
if(s[j]=='+') now+=(1<<j);
//首先 一开始的读入我们直接转化为对应的二进制状态
num[now].up=round(tmp*100.0);
num[now].dow=100;
int x=gcd((num[now].up>0 ? num[now].up:-num[now].up),(num[now].dow>0 ? num[now].dow:-num[now].dow));
if(num[now].dow<0) num[now].up=-num[now].up,num[now].dow=-num[now].dow;
num[now].up/=x;num[now].dow/=x;
//然后是对于每一种状态对应函数值从小数维护成分数
}
dfs_ans(0,0);
print_ans(0,0);
return 0;
}