题目链接

题意分析

这道题就是上来一个多项式

\[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
#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;i0 ? 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;
}